一旦wrong anwser
可以从以下几个方面考虑
1 算法是否正确
2 特例有没有
3 题意有没有理解
#include<iostream>
#include<cstring>using namespace std;
struct Node
{
short int dest;
Node *next;
};
struct Graph
{
Node *next;
}ga[20001],gt[20001];
int n,m;
short int path[20001];
char in[20001];
char out[20001];
char vis[20001];
short int part[20001];
//char map[20001][20001];
void addedge(Graph g[],int i,int j)
{
Node *l=new Node;
l->dest=j;
l->next=g[i].next;
g[i].next=l;
}
void dfsa(int u)
{
Node *l=ga[u].next;
if(!vis[u])
{
vis[u]=1;
for(l;l!=NULL;l=l->next)
dfsa(l->dest);
path[0]++;
path[path[0]]=u;
}
}
void dfst(int u)
{
Node *l=gt[u].next;
if(!vis[u])
{
vis[u]=1;
for(l;l!=NULL;l=l->next)
dfst(l->dest);
part[u]=part[0];
}
}
void k()
{
int i;
path[0]=0;
memset(vis,0,sizeof(vis));
//搜索原图
for(i=1;i<=n;i++)
{
if(!vis[i])
dfsa(i);
}
memset(vis,0,sizeof(vis));
// int sum=0;
part[0]=0;
for(i=n;i>=1;i--)
{
if(!vis[path[i]])
{
part[0]++;
dfst(path[i]);
}
}
//创建新图
Node *l;
// memset(map,0,sizeof(map));
memset(in,0,sizeof(in));
memset(out,0,sizeof(out));
int a=0;
int b=0;int sum;
for(i=1;i<=n;i++)// 剔除连通分量
{
for(l=ga[i].next;l!=NULL;l=l->next)
{
int k=part[i];
int j=part[l->dest];
if(j!=k)
{
in[j]=1;
out[k]=1;
}
}
}
for(i=1;i<=part[0];i++)
{
if(in[i]==0) a++;
if(out[i]==0) b++;
}
if(a>b)
sum=a;
else sum=b;
if(sum==1)
sum=0;
printf("%d ",sum);
}
int main()
{
int t;
int a,b,i;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
ga[i].next=gt[i].next=NULL;
while(m--)
{
scanf("%d%d",&a,&b);
addedge(ga,a,b);
addedge(gt,b,a);
}
k();
}
return 0;
}