本来这几天打算做2-SAT的，昨天和zzy看了算法之后，其中说到需要解强连通分量,于是便开始学习了。虽然以前也学习过强连通分量的算法，那时只知道一个就是Kasaraju算法，当时对于其两次DFS先正搜再反搜的顺序不以为然，我坚定地先反搜再正搜，结果果断的WA了！zzy那时秒A过的.... 于是我便没有了兴趣。直到今天凭借着郭大牛的手稿理解的Tarjan的流程。便来重新解决这个大牛的问题......
在A这题中我学会了1.Tarjan算法。2.缩点（虽然缩点后构成了一个新图，但是我确实是缩点了！！）3.这是一道模拟题。4.和zzy讨论出了很好的解法，比直接做方便多了(虽然代码依旧很长....)
1.Tarjan算法->照旧，等待我把强连通的题A的差不多了就会写一篇总结。
2.缩点。在Tarjan出队的过程中，把每个点都标记为他的强连通分量的序号。通过原有的边来构建新图，原有的两边为不同强连通中的点时，对两个缩点进行连边。
3.模拟题。编码能力有提升~
4.这是配合问题 嗯~~
#include<iostream> #include<stdio.h> #include<stack> #define MAXN 10 #define MAXM 50 using namespace std;struct Node {int v;Node *next; }Edge[2][MAXM],*ptr[2][MAXN];int N,M;int min( int a,int b ){ return a<b?a:b; }void addEdge( int u,int v,int num,int g ) {Node *p=&Edge[g][num];p->v=v;p->next=ptr[g][u];ptr[g][u]=p; } int DFN[MAXN],LOW[MAXN]; int cnt; bool visited[MAXN]; bool inS[MAXN]; stack<int>myStack; int SCC; int P[MAXN]; int SCCNum[MAXN]; bool FINISH;void tarjan(int u) {LOW[u]=DFN[u]=++cnt;visited[u]=true;inS[u]=true;myStack.push(u);Node *p=ptr[0][u];while( p ){if( !visited[p->v] ){tarjan( p->v );LOW[u]=min( LOW[u],LOW[p->v] );}else if( inS[p->v] )LOW[u]=min( LOW[u],DFN[p->v] );p=p->next;}if( DFN[u]==LOW[u] ){++SCC;int v;do {v=myStack.top();printf( "%d\n",v );myStack.pop();P[v]=SCC;SCCNum[SCC]++;inS[v]=false;}while( !(u==v) );} }bool DFS(int pre ) {visited[pre]=true;int i,sum=0;for( i=1;i<=SCC;i++ ) sum+=visited[i];if( sum==SCC ) FINISH=true;Node *p=ptr[1][pre];while( p ){DFS( p->v );if( FINISH )return true; }return FINISH; }int main() {while( scanf( "%d %d",&N,&M )!=EOF ){int u,v,i;for( i=1;i<=M;i++ ){scanf( "%d %d",&u,&v );addEdge( u,v,i,0 );}FINISH=false;memset( DFN,0,sizeof(DFN) );memset( LOW,0,sizeof(LOW) );memset( visited,0,sizeof(visited) );memset( inS,0,sizeof(inS) );memset( SCCNum,0,sizeof(SCCNum) );cnt=0;SCC=0;for( i=1;i<=N;i++ )if( !visited[i] )tarjan(i);int g=0;for( i=1;i<=N;i++ ){Node *p=ptr[0][i];while( p ){if( P[i]!=P[p->v] )addEdge( P[p->v],P[i],++g,1 );p=p->next;}}for( i=1;i<=SCC;i++ ){memset( visited,0,sizeof(visited) );DFS( i );if( FINISH )break;}if( i<=SCC )printf( "%d\n",SCCNum[i] );elseprintf( "0\n" );}return 0; }