#include <iostream>
#include <ctime>
#include <cstdlib>
#include <cstring>
using namespace std;
const int MAX=10010;

struct Fu
{
    int x;
    int cut;
    int kind;
} fu[MAX];

int N,M;
int graph[MAX][MAX];
int flag[MAX];
int counts=1;
int kind=0;
void DFS(int x);
int compare(const void *a,const void *b);
int compare1(const void *a,const void *b);
int main()
{
    cin>>N>>M;
    int i,j;
    int x,y;
    for(i=1;i<=N;i++)
    	fu[i].x=i;
    for(i=1; i<=M; i++)
    {
        cin>>x>>y;
        graph[x][y]=1;
    }
    clock_t start_time=clock();///程序开始运行

    for(i=1; i<=N; i++)
    {
		if(!flag[i])
            DFS(i);
    }

    for(i=2; i<=N; i++)
        for(j=1; j<i; j++)
        {
            if(graph[i][j]+graph[j][i]==1)
            {
                graph[i][j]=(graph[i][j]+1)%2;
                graph[j][i]=(graph[j][i]+1)%2;
            }

        }
    qsort(&fu[1],N,sizeof(struct Fu),compare);
    memset(&flag[1],0,(N+1)*sizeof(int));

    for(i=1; i<=N; i++)
        if(!flag[fu[i].x])
        {
            kind++;
            DFS(fu[i].x);
        }
    int ans[MAX];
    int flags;
    memset(&ans[1],0,kind*sizeof(int));
	counts=0;
    for(i=2; i<=N; i++)
        for(j=1; j<i; j++)
        {
            if(graph[i][j]+graph[j][i]==1)
            {
                graph[i][j]=(graph[i][j]+1)%2;
                graph[j][i]=(graph[j][i]+1)%2;
            }
        }

    for(i=1; i<=N; i++)
    {
        flags=0;
        if(ans[fu[i].kind]!=-1)
            for(j=i+1; j<=N; j++)
            {
                if(graph[i][j]&&fu[i].kind!=fu[j].kind)
                        ans[fu[i].kind]=-1;

                if(graph[j][i]&&fu[i].kind!=fu[j].kind)
                        ans[fu[j].kind]=-1;
            }
    }
    int mark=0,result=0;
    for(i=1;i<=kind;i++)
        if(ans[i]!=-1)
        {
            mark++;
            if(mark==1)
                result=i;
        }
    if(mark>1)  
        cout<<0;
    if(mark==1)
    {
    mark=0;
    for(i=1;i<=N;i++)
        if(fu[i].kind==result)
        mark++;
    cout<<mark;
    }
    
    return 0;
}

void DFS(int x)
{
    int i;
    flag[x]=1;
    fu[x].kind=kind;
    for(i=1; i<=N; i++)
    {
        if(graph[x][i]&&!flag[i])
            DFS(i);
    }
    fu[x].cut=counts++;
}
int compare(const void *a,const void *b)
{
    return ((struct Fu*)b)->cut-((struct Fu*)a)->cut;

}

• Re:为什么测了好多数据都是对的，但提交之后还是答案错误？ (2756) 1340502116 2016-01-29 13:48:18