強連通圖： 在一個有向圖中，所有頂點都能互相到達則為強連通圖

強連通分量：對于一個有向非強連通圖的一個子圖強連通，則這個子圖稱為強連通分量

targan：用于求有向圖強連通分量的算法，該算法基于對圖的dfs，即每個強連通分量為dfs的一顆子樹

              即從某一個頂點開始往下dfs并且把點入棧，如果走到不能走時，說明以改點是一個強連通分量

              如果下一個節點已經在棧中，說明存在一個強連通分量，然后回溯，當回溯到那個點時，此時在

              棧中位于改點之上的點為一個強連通分量！

算法實現：我們定義數組 dfn[i]為i點在dfs當中的編號即時間戳，low[i]為i點在子樹中能到達的最小的編號，

                  所以當dfn[i]==low[i]時說明當前存在一個強連通分量

                 具體可以參見博客：targan算法有向圖強連通分量

算法例子：

1，poj3114

Description

In the year 2050, after different attempts of the UN to maintain peace in the world, the third world war broke out. The importance of industrial, commercial and military secrets obliges all the countries to use extremely sophisticated espionage services, so that each city in the world has at least one spy of each country. These spies need to communicate with other spies, informers as well as their headquarters during their actions. Unluckily there doesn’t exist a secure way for a spy to communicate during the war period, therefore the messages are always sent in code so that only the addressee is able to read the message and understand its meaning.

The spies use the only service that functions during the war period, the post. Each city has a postal agency where the letters are sent. The letters can be sent directly to their destination or to other postal agencies, until the letter arrives at the postal agency of the destination city, if possible.

The postal agency in city A can send a PRinted letter to the postal agency in city B if there is an agreement on sending letters, which determines the time, in hours, that a letter takes to reach city B from city A (and not necessarily the opposite). If there is no agreement between the agencies A and B, the agency A can try to send the letter to any agency so that the letter can reach its destination as early as possible

Some agencies are connected with electronic communication media, such as satellites and optical fibers. Before the war, these connections could reach all the agencies, making that a letter could be sent instantly. But during the period of hostilities every country starts to control electronic communication and an agency can only send a letter to another agency by electronic media (or instantly) if they are in the same country. Two agencies, A and B, are in the same country if a printed letter sent from any one of the agencies can be delivered to the other one.

The espionage service of your country has managed to obtain the content of all the agreements on sending messages existing in the world and desires to find out the minimum time to send a letter between different pairs of cities. Are you capable of helping them?

Input

The input contains several test cases. The first line of each test case contains two integer separated by a space, N (1 ≤ N ≤ 500) and E (0 ≤ E ≤ N²), indicating the numbers of cities (numbered from 1 to N) and of agreements on sending messages, respectively. Following them, then, E lines, each containing three integers separated by spaces, X, Y and H (1 ≤ X, Y ≤ N, 1 ≤ H ≤ 1000), indicating that there exist an agreement to send a printed letter from city X to city Y, and that such a letter will be delivered in H hours.

After that, there will be a line with an integer K (0 ≤ K ≤ 100), the number of queries. Finally, there will be K lines, each representing a query and containing two integers separated by a space, Oand D (1 ≤ O, D ≤ N). You must determine the minimum time to send a letter from city O to city D.

The end of the input is indicated by N = 0.

Output

For each test case your program should produce K lines of output. The I-th line should contain an integer M, the minimum time, in hours, to send a letter in the I-th query. If there aren’t communication media between the cities of the query, you should print “Nao e possivel entregar a carta” (“It’s impossible to deliver the letter”).

Print a blank line after each test case.

Sample Input

4 51 2 52 1 103 4 84 3 72 3 651 21 31 44 34 13 31 2 102 3 13 2 131 33 13 20 0
Sample Output
0660Nao e possivel entregar a carta10Nao e possivel entregar a carta0
Source
South America 2006, Brazil Subregion
題目思路：
                 給你一張n個點，m條邊的有向圖和k詢問，每次詢問從u到v的最短路，對于圖中，強連通分量中的點的距離為0
                 所以我們可以先用targan縮點，即一個強連通分量縮成一個點，然后重新建圖即可
AC代碼：
#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<queue>using namespace std;const int maxn = 550;const int inf = 1e8;struct st{    int v,w,nex;}tedge[maxn*maxn],edge[maxn*maxn];int n,m,e,index,cnt,top;int hed[maxn],thed[maxn],dis[maxn],vis[maxn];int dfn[maxn],low[maxn],stack[maxn],belon[maxn];void init(){    memset(hed,-1,sizeof(hed));    memset(thed,-1,sizeof(hed));    memset(vis,0,sizeof(vis));    memset(dfn,0,sizeof(dfn));    e=1;index=top=cnt=0;}void tadd(int u,int v,int w){    tedge[e].v=v,tedge[e].w=w,tedge[e].nex=thed[u],thed[u]=e++;}void add(int u,int v,int w){    edge[e].v=v,edge[e].w=w,edge[e].nex=hed[u],hed[u]=e++;}void targan(int i){    dfn[i]=low[i]=++index;    stack[top++]=i;    vis[i]=1;    for(int j=thed[i];~j;j=tedge[j].nex){        int v = tedge[j].v;        if(!dfn[v]){            targan(v);            if(low[v]<low[i])low[i]=low[v];        }else if(vis[v]){            if(dfn[v]<low[i])low[i]=dfn[v];        }    }    if(low[i]==dfn[i]){        cnt++;        int j;        do{            j = stack[--top];            belon[j]=cnt;            vis[j]=0;        }while(j!=i);    }}void spfa(int u){    for(int i=1;i<=n;i++)        dis[i]=inf,vis[i]=0;    dis[u]=0;    priority_queue<pair<int,int> >q;    q.push(make_pair(-dis[u],u));    while(!q.empty()){        int u = q.top().second;q.pop();        if(vis[u])continue;        vis[u]=1;        for(int i=hed[u];~i;i=edge[i].nex){            int v = edge[i].v;            if(dis[v]>dis[u]+edge[i].w){                dis[v]=dis[u]+edge[i].w;                if(!vis[v]){                    q.push(make_pair(-dis[v],v));                }            }        }    }}int main(){    while(cin>>n>>m,n+m){        init();        while(m--){            int u,v,w;scanf("%d%d%d",&u,&v,&w);            tadd(u,v,w);        }        for(int i=1;i<=n;i++){            if(!dfn[i])targan(i);        }        e=1;        for(int i=1;i<=n;i++){            for(int j=thed[i];~j;j=tedge[j].nex){                int v = tedge[j].v;                if(belon[i]!=belon[v])add(belon[i],belon[v],tedge[j].w);            }        }        int k;scanf("%d",&k);        while(k--){            int u,v;scanf("%d%d",&u,&v);            if(belon[u]==belon[v]){                printf("0/n");                continue;            }            spfa(belon[u]);            if(dis[belon[v]]==inf)printf("Nao e possivel entregar a carta/n");            else printf("%d/n",dis[belon[v]]);        }        printf("/n");    }    return 0;}
poj3160：
Father Christmas flymouse
Time Limit: 1000MS
 
Memory Limit: 131072K
Total Submissions: 3303
 
Accepted: 1120
Description
After retirement as contestant from WHU ACM Team, flymouse volunteered to do the odds and ends such as cleaning out the computer lab for training as extension of his contribution to the team. When Christmas came, flymouse played Father Christmas to give gifts to the team members. The team members lived in distinct rooms in different buildings on the campus. To save vigor, flymouse decided to choose only one of those rooms as the place to start his journey and follow directed paths to visit one room after another and give out gifts en passant until he could reach no more unvisited rooms.
During the days on the team, flymouse left different impressions on his teammates at the time. Some of them, like LiZhiXu, with whom flymouse shared a lot of candies, would surely sing flymouse’s deeds of generosity, while the others, like snoopy, would never let flymouse off for his idleness. flymouse was able to use some kind of comfort index to quantitize whether better or worse he would feel after hearing the Words from the gift recipients (positive for better and negative for worse). When arriving at a room, he chould choose to enter and give out a gift and hear the words from the recipient, or bypass the room in silence. He could arrive at a room more than once but never enter it a second time. He wanted to maximize the the sum of comfort indices accumulated along his journey.
Input
The input contains several test cases. Each test cases start with two integers N and M not exceeding 30 000 and 150 000 respectively on the first line, meaning that there were N team members living in N distinct rooms and M direct paths. On the next N lines there are N integers, one on each line, the i-th of which gives the comfort index of the words of the team member in the i-th room. Then follow M lines, each containing two integers i and j indicating a directed path from the i-th room to the j-th one. Process to end of file.
Output
For each test case, output one line with only the maximized sum of accumulated comfort indices.
Sample Input
2 214210 11 0
Sample Output
35
Hint
32-bit signed integer type is capable of doing all arithmetic.
Source
POJ Monthly--2006.12.31, Sempr
題目思路：
                給你一張n點m條邊的有向圖，以及每個點的權值可以為負的，求從某一個點出發沿著給出的邊一直走直到不能
               走為止的最大權值，即最長路，對于一個點來說，你可以獲得權值最多一次，但可以經過多次，所以我們可以忽略掉負值
               應為存在強連通分量即有環，所以我們可以先用targan縮點，因為可能存在多個圖，所以我們建一個超級原點0
              這樣我們就可以從0點跑一遍spfa最長路即可
AC代碼：
#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<queue>using namespace std;const int maxn = 3e4+100;const int inf = 1e9;struct st{    int v,w,nex;}tedge[maxn*10],edge[maxn*10];int n,m,e,index,cnt,top;int hed[maxn],thed[maxn],dis[maxn],vis[maxn],out[maxn];int dfn[maxn],low[maxn],stack[maxn],belon[maxn],tw[maxn],w[maxn];void init(){    memset(hed,-1,sizeof(hed));    memset(thed,-1,sizeof(hed));    memset(vis,0,sizeof(vis));    memset(dfn,0,sizeof(dfn));    memset(w,0,sizeof(w));    e=1;index=top=cnt=0;}void tadd(int u,int v){    tedge[e].v=v,tedge[e].nex=thed[u],thed[u]=e++;}void add(int u,int v,int w){    edge[e].v=v,edge[e].w=w,edge[e].nex=hed[u],hed[u]=e++;}void targan(int i){    dfn[i]=low[i]=++index;    stack[top++]=i;    vis[i]=1;    for(int j=thed[i];~j;j=tedge[j].nex){        int v = tedge[j].v;        if(!dfn[v]){            targan(v);            if(low[v]<low[i])low[i]=low[v];        }else if(vis[v]){            if(dfn[v]<low[i])low[i]=dfn[v];        }    }    if(low[i]==dfn[i]){        cnt++;        int j;        do{            j = stack[--top];            belon[j]=cnt;            vis[j]=0;            if(tw[j]>0)w[cnt]+=tw[j];        }while(j!=i);    }}int spfa(){    int ans = 0;    queue<int>q;    for(int i=0;i<=cnt;i++)dis[i]=0;    q.push(0);    while(!q.empty()){        int u = q.front();q.pop();        vis[u]=0;        for(int i=hed[u];~i;i=edge[i].nex){            int v = edge[i].v;            if(dis[v]<dis[u]+edge[i].w){                dis[v]=dis[u]+edge[i].w;                if(!vis[v]){                    q.push(v);                     vis[v]=1;                }            }        }    }    for(int i=1;i<=cnt;i++)        if(!out[i])ans=max(ans,dis[i]);    return ans;}int main(){    while(cin>>n>>m){        init();        for(int i=1;i<=n;i++)scanf("%d",&tw[i]);        while(m--){            int u,v;scanf("%d%d",&u,&v);            u++,v++;            tadd(u,v);        }        for(int i=1;i<=n;i++){            if(!dfn[i])targan(i);        }        e=0;        int in[maxn];        memset(in,0,sizeof(in));        memset(out,0,sizeof(out));        for(int i=1;i<=n;i++){            for(int j=thed[i];~j;j=tedge[j].nex){                int v = tedge[j].v;                if(belon[i]!=belon[v]){                    in[belon[v]]++;                    out[belon[i]]++;                    add(belon[i],belon[v],w[belon[v]]);                }            }        }        for(int i=1;i<=cnt;i++){            if(!in[i]){                add(0,i,w[i]);            }        }        printf("%d/n",spfa());    }    return 0;}