强连通分量：若在一个点集U中，对于任意两个点u,v（u,v∈U && u != v），即存在一条从 u 到 v 的路径，也存在一条从 v 到 u 的路径，则称此集合为强连通分量。
Taijan算法：
借助 index[ ] 和 rv[ ] 两个数组，rv[ u ] 记录DFS访问 u 时 的时间戳，index[ u ] 记录在DFS树中，u及其子孙能通过反向边连接到的正在等待DFS回溯的点中rv[]的最小值，也可以理解成最远的祖先。
若在回溯过程中有 index[ u ] != rv[ u ] , 并将其压入栈中。
若在回溯过程中有 index[ u ] == rv[ u ],则 u 为其所在的强连通分量中第一个被访问的点。此时应将栈中的u及在u之后被压入的点弹出。
POJ 3114 ：强连通分量 + 最短路。不再赘述。
HDU 2767：若图已联通，则输出0。否则统计各连通分量形成的缩点的出入度，id，od，输出max（id,od）.
POJ 3114
#include#include #include #include #include #include #include #define LL long long #define ULL unsigned long long #define PI (acos(-1.0)) #define EPS (1e-10) #pragma comment(linker,"/STACK:102400000,1024000") using namespace std; const int MAX = (1<<30); struct P { int u,v,w; }p[250010]; struct N { int v,next; }e[250100]; int index[20100]; int head[20100]; int rv[20100]; int ty[20100]; int ry[20100]; int st[20100]; bool id[20100]; bool od[20100]; int Top,Time,St_Top; void link(int u,int v) { e[Top].next = head[u]; e[Top].v = v; head[u] = Top++; } void dfs(int s) { rv[s] = index[s] = Time++; st[St_Top++] = s; for(int p = head[s]; p != -1; p = e[p].next) { if(rv[e[p].v] == -1) { dfs(e[p].v); index[s] = min(index[s],index[e[p].v]); } else if(ty[e[p].v] == -1) { index[s] = min(index[s],rv[e[p].v]); } } if(index[s] == rv[s]) { ry[Top] = s; while(true) { St_Top--; int x = st[St_Top]; ty[x] = Top; if(x == s) break; } Top++; } } int dis[510]; void sp(int u,int v,int n,int m) { if(ty[u] == ty[v]) { printf("0\n"); return ; } int i,j; bool mark; for(i = 0;i < Top; ++i) { dis[i] = MAX; } dis[ty[u]] = 0; for(i = 0;i < Top; ++i) { mark = true; for(j = 0;j < m; ++j) { if(ty[p[j].v] != ty[p[j].u] && dis[ty[p[j].u]] + p[j].w < dis[ty[p[j].v]]) { dis[ty[p[j].v]] = dis[ty[p[j].u]] + p[j].w; mark = false; } } if(mark) break; } if(dis[ty[v]] == MAX) { printf("Nao e possivel entregar a carta\n"); } else { printf("%d\n",dis[ty[v]]); } } int main() { int n,m,i,u,v; while(scanf("%d %d",&n,&m) && n) { memset(head,-1,sizeof(int)*(n+3)); memset(rv,-1,sizeof(int)*(n+3)); memset(ty,-1,sizeof(int)*(n+3)); Top = 0; for(i = 0; i < m; ++i) { scanf("%d %d %d",&p[i].u,&p[i].v,&p[i].w); link(p[i].u,p[i].v); } Top = 0,Time = 0,St_Top = 0; for(i = 1; i <= n; ++i) { if(rv[i] == -1) { dfs(i); } } int k; scanf("%d",&k); while(k--) { scanf("%d %d",&u,&v); sp(u,v,n,m); } printf("\n"); } return 0; }
HDU 2767 :
#include#include #include #include #include #include #include #define LL long long #define ULL unsigned long long #define PI (acos(-1.0)) #define EPS (1e-10) #pragma comment(linker,"/STACK:102400000,1024000") using namespace std; const int MAX = (1<<30); struct N { int v,next; }e[50100]; int index[20100]; int head[20100]; int rv[20100]; int ty[20100]; int ry[20100]; int st[20100]; bool id[20100]; bool od[20100]; int Top,Time,St_Top; void link(int u,int v) { e[Top].next = head[u]; e[Top].v = v; head[u] = Top++; } void dfs(int s) { rv[s] = index[s] = Time++; st[St_Top++] = s; for(int p = head[s]; p != -1; p = e[p].next) { if(rv[e[p].v] == -1) { dfs(e[p].v); index[s] = min(index[s],index[e[p].v]); } else if(ty[e[p].v] == -1) { index[s] = min(index[s],rv[e[p].v]); } } if(index[s] == rv[s]) { ry[Top] = s; while(true) { St_Top--; int x = st[St_Top]; ty[x] = Top; if(x == s) break; } Top++; } } int main() { //freopen("b.in","r",stdin); int n,m,i,p,u,v,T; scanf("%d",&T); while(T--) { scanf("%d %d",&n,&m); memset(head,-1,sizeof(int)*(n+3)); memset(rv,-1,sizeof(int)*(n+3)); memset(ty,-1,sizeof(int)*(n+3)); Top = 0; for(i = 0; i < m; ++i) { scanf("%d %d",&u,&v); link(u,v); } Top = 0,Time = 0,St_Top = 0; for(i = 1; i <= n; ++i) { if(rv[i] == -1) { dfs(i); } } memset(id,false,sizeof(bool)*(Top+3)); memset(od,false,sizeof(bool)*(Top+3)); for(i = 1;i <= n; ++i) { for(p = head[i]; p != -1; p = e[p].next) { if(ty[i] != ty[e[p].v]) { od[ty[i]] = true; id[ty[e[p].v]] = true; } } } int a1,a2; for(i = 0,a1 = 0,a2 = 0;i < Top; ++i) { if(od[i] == false) { a1++; } if(id[i] == false) { a2++; } } if(Top == 1) { printf("0\n"); } else { if(a1 > a2) printf("%d\n",a1); else printf("%d\n",a2); } } return 0; }