1 #include<stdio.h> 2 #include<string.h> 3 #include<stdlib.h> 4 #include<math.h> 5 #include<algorithm> 6 #include<iostream> 7 #include<set> 8 #include<stack> 9 #include<queue> 10 #include<map> 11 #include<vector> 12 using namespace std; 13 14 const int maxn = 105; 15 const int maxm = 1005; 16 const int inf = 0x3f3f3f3f; 17 const double pi = acos(-1.0); 18 const double eps = 1e-8; 19 20 struct Edge{ 21 int u,v,next; 22 }edge[ maxn*maxn ]; 23 int cnt,head[ maxn ]; 24 int vis[ maxn ],belong[ maxn ]; 25 stack<int>s; 26 int dfn[ maxn ],low[ maxn ]; 27 int Cnt ,id ; 28 29 void init(){ 30 while( !s.empty() ) 31 s.pop(); 32 Cnt = 0; 33 id = 0; 34 memset( dfn,-1,sizeof( dfn ) ); 35 memset( low,-1,sizeof( low ) ); 36 cnt = 0; 37 memset( head,-1,sizeof( head ) ); 38 } 39 40 void addedge( int a,int b ){ 41 edge[ cnt ].u = a; 42 edge[ cnt ].v = b; 43 edge[ cnt ].next = head[ a ]; 44 head[ a ] = cnt++; 45 } 46 47 void tarjan( int cur ){ 48 dfn[ cur ] = low[ cur ] = id++; 49 vis[ cur ] = 1; 50 s.push( cur ); 51 for( int i=head[ cur ];i!=-1;i=edge[i].next ){ 52 int nxt = edge[i].v; 53 if( dfn[ nxt ]==-1 ){ 54 tarjan( nxt ); 55 low[ cur ] = min( low[ nxt ],low[ cur ] ); 56 } 57 else if( vis[ nxt ]==1 ){ 58 low[ cur ] = min( dfn[ nxt ],low[ cur ] ); 59 } 60 } 61 if( dfn[ cur ]==low[ cur ] ){ 62 Cnt ++; 63 while( 1 ){ 64 int tmp = s.top(); 65 s.pop(); 66 vis[ tmp ] = 0; 67 belong[ tmp ] = Cnt; 68 if( tmp==cur ) break; 69 } 70 } 71 } 72 73 int main(){ 74 int n,m; 75 while( scanf("%d%d",&n,&m)==2 ){ 76 int a,b; 77 init(); 78 while( m-- ){ 79 scanf("%d%d",&a,&b); 80 addedge( a,b ); 81 } 82 for( int i=1;i<=n;i++ ){ 83 if( dfn[i]==-1 ){ 84 tarjan( i ); 85 } 86 } 87 printf("缩点 = %d ",Cnt); 88 } 89 return 0; 90 }