考察知识点：强连通分量的的求法
bug：注意强连通分量个数只有一个的情况
思维：这个转化倒是知道，但是知识点不足，还有一个更重要的是邻接表的写法和邻接矩阵的写法有很多的不同，特别是在第二次dfs的时候注意元素的表示不是i了而应该是
for( int i= 0; i<num; ++i)
if( flag[ b[cur][i] ] == 0 )
visttwo(b[cur][i],sig);
再贴一个tyvj的纯裸的强连通分量：tvvj1111
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
#define max 210
int a[max][max],b[max][max];//a为图G的邻接矩阵，b为图G的反图的邻接矩阵
int bleg[max];
int flag[max];
int numb[max];
int n;
void vistone(int cur,int &sig)
{
flag[cur] = 1;
for( int i=1; i<=n; ++i)
if( flag[i] == 0 && a[cur][i] == 1 )
vistone(i,sig );
numb[++sig] = cur;
}
void visttwo( int cur ,int sig)
{
flag[cur] = 1;
bleg[cur] =sig;
for( int i= 1; i<=n; ++i)
if( flag[i] == 0 && b[cur][i] == 1 )
visttwo(i,sig);
}
int korareju()
{
int sig =0;
memset(flag,0,sizeof(flag));
for( int i=1;i<=n; ++i)
if( flag[i] == 0)
vistone(i,sig);
memset(flag,0,sizeof(flag));
sig=0;
for(int i=n; i>=1; --i )
if( flag[ numb [i] ] == 0 )
{
visttwo(numb[i], (++sig) );
}
return sig;
}
int main()
{
scanf("%d",&n);
int i = 0;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
while( (i++)<n )
{
while( true )
{
int x;
scanf("%d",&x);
if( x == 0)
break;
a[i][x] = 1;
b[x][i] = 1;
}
}
int w = korareju();
printf("%d\n",w);
return 0;
}
#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
using namespace std;
#define max 20010
vector< int > a[max],b[max];//a为图G的邻接矩阵，b为图G的反图的邻接矩阵
int bleg[max];
int flag[max];
int numb[max];
int out[max];
int in[max];
int n;
void vistone(int cur,int &sig)
{
flag[cur] = 1;
int num = a[cur].size();
for( int i=0; i<num; ++i)
if( flag[ a[cur][i] ] == 0 )
vistone(a[cur][i],sig );
numb[++sig] = cur;
}
void visttwo( int cur ,int sig)
{
flag[cur] = 1;
bleg[cur] =sig;
int num = b[cur].size();
for( int i= 0; i<num; ++i)
if( flag[ b[cur][i] ] == 0 )
visttwo(b[cur][i],sig);
}
int korareju()
{
int sig =0;
memset(flag,0,sizeof(flag));
for( int i=1;i<=n; ++i)
if( flag[i] == 0)
{
vistone(i,sig);
}
memset(flag,0,sizeof(flag));
sig=0;
for(int i=n; i>=1; --i )
if( flag[ numb[i] ] == 0 )
{
visttwo( numb[i], (++sig) );
}
return sig;
}
int main()
{
int m;
while( scanf("%d%d",&n,&m) == 2 )
{
int k = 0;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(numb,0,sizeof(numb));
memset(out,0,sizeof(out));
memset(in,0,sizeof(in));
memset(bleg,0,sizeof(bleg));
while( (k++)<m )
{
int x,y;
scanf("%d%d",&x,&y);
a[x].push_back(y);
b[y].push_back(x);
}
if( n <= 1 )
{
printf("0\n");
continue;
}
int w = korareju();
if( w == 1 )
{
printf("0\n");
continue;
}
for( int i=1; i<=n; ++i )
{
int num = a[i].size();
for(int j=0; j<num; ++j)
if( bleg[i] != bleg[ a[i][j] ] )
{
out[bleg[i]]++;
in[ bleg[ a[i][j] ] ]++;
}
}
int od=0;
int id=0;
for( int i= 1; i<=w; ++i)
{
if( out[i] == 0 )
od++;
if( in[i] == 0 )
id++;
}
int max0=od;
if(max0<id)
max0=id;
printf("%d\n",max0);
}
return 0;
}