2746600_ac_328ms_25744k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <vector>
# define MAXV 1000

using namespace std;

int N;
int M;
int cnt;
int order[MAXV], id[MAXV];
int visited[MAXV], in[MAXV];
typedef struct node
{
	int adjvex;
	struct node *next;
}EdgeNode;
typedef struct vnode
{
	EdgeNode *firstedge;
}VertexNode;
typedef VertexNode AdjList[MAXV];
typedef struct ALGraph
{
	AdjList adjlist;
}Graphic;

Graphic GA, GB;
struct NODE
{
	int st,ed;
}Edge[6001];
int flag, T;
vector <int> tree[MAXV];

void insert(int u, int v)
{
	EdgeNode *s;

	s = (EdgeNode *)malloc(sizeof(EdgeNode));
	s->adjvex = v;
	s->next = GA.adjlist[u].firstedge;
	GA.adjlist[u].firstedge = s;
	s = (EdgeNode *)malloc(sizeof(EdgeNode));
	s->adjvex = u;
	s->next = GB.adjlist[v].firstedge;
	GB.adjlist[v].firstedge = s;
}

void input()
{
	int u, v, i;

	memset(in,0,sizeof(in));
	for(i = 0; i < M; i++)
	{
		scanf("%d%d",&u,&v);
		Edge[i].st = u-1,Edge[i].ed = v-1;
		insert(u-1,v-1);
	}
}

void init()
{
	int i;

	scanf("%d%d",&N,&M);
	for(i = 0; i < N; i++)
	{
		tree[i].clear();
		GA.adjlist[i].firstedge = NULL;
		GB.adjlist[i].firstedge = NULL;
	}
}

void dfs_b(int v)
{
	EdgeNode *s;

	visited[v] = 1;
	s = GB.adjlist[v].firstedge;
	while(s)
	{
		if(!visited[s->adjvex])
			dfs_b(s->adjvex);
		s = s->next;
	}
	order[cnt++] = v;
}

void dfs_a(int v)
{
	EdgeNode *s;

	visited[v] = 1;
	id[v] = cnt;
	s = GA.adjlist[v].firstedge;
	while(s)
	{
		if(!visited[s->adjvex])
		{
			dfs_a(s->adjvex);
		}
		s = s->next;
	}
}

void dfs(int v,int nn)
{
	int i;

	visited[v] = 1;
	if(nn==T)
		flag = 1;
	for(i = 0; i < tree[v].size(); i++)
	{
		if(!visited[tree[v][i]])
		{
			dfs(tree[v][i],nn+1);
			visited[tree[v][i]] = 0;
		}
	}
}

void solve()
{
	int i, t, pos;

	cnt = 0;
	memset(visited,0,sizeof(visited));
	for(i = 0; i < N; i++)
		if(!visited[i])
			dfs_b(i);
	cnt = 0;
	memset(visited,0,sizeof(visited));
	for(i = N-1; i >= 0; i--)
		if(!visited[order[i]])
		{
			dfs_a(order[i]);
			cnt++;
		}



	for(i = 0; i < M; i++)
	{
		if(id[Edge[i].st]!=id[Edge[i].ed])
		{
			in[id[Edge[i].ed]]++;
			tree[id[Edge[i].st]].push_back(id[Edge[i].ed]);
		}
	}
	T = t = cnt;
	cnt = 0;
	for(i = 0; i < t; i++)
	{
		if(in[i]==0)
		{
			pos = i;
			cnt++;
		}
	}
	if(cnt==1)
	{
		memset(visited,0,sizeof(visited));
		flag = 0;
		dfs(pos,1);
		if(flag)
			printf("Yes\n");
		else
			printf("No\n");
	}
	else
		printf("No\n");
}

int main()
{
	int cas;

	scanf("%d",&cas);
	while(cas--)
	{
		init();
		input();
		solve();
	}
	return 1;
}