博客

题目描述

写程序判断有向图是否存在环。有向图的输入用n个二元组表示(u,v)，表示从u到v有一条有向边，起点是u，终点是v。

输入格式

输入包括多组测试数据，每组测试数据首先是正整数n和m，表示有向图有n个节点（编号从1到n），m条有向边，接下来是m行，每行为两个正整数u和v，用空格隔开，表示从节点u到节点v有一条有向边，u和v都大于等于1且小于等于n

最后一行为0 0，表示测试数据结束

有向图的节点个数不超过100个，边的个数不超过1000

输出格式

如果该有向图存在环，输出YES，否则输出NO

输入样例

11 10
1 2
2 3
4 3
5 4
6 5
3 9
10 9
9 11
7 8
8 11
2 2
1 2
2 1
3 3
1 2
2 3
3 1
0 0

输出样例

NO
YES
YES

代码展示

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

#define INFO_MAX_SIZE 20
#define MAX_SIZE 200
 //领接矩阵存储的图
struct Graph{
	int vexNumber;
	string vexInfo[INFO_MAX_SIZE];
	int adjMatrix[MAX_SIZE][MAX_SIZE];
};
 //弧结点定义
struct ArcNode{
	int weight;//弧上的信息部分
	int adj;//邻接点的序号
	ArcNode *nextarc;
};
 //顶点结点定义
struct VexNode{
	string Info;
	ArcNode *firstarc;
};
 //领接表结构的图的定义
struct linkGraph{
	VexNode *vexes;
	int vexnumber;
};

struct tempNode{
	int col;
	int row;
	//tempNode *next;
};

struct temp{
	int num;
	tempNode *docu;
};


int preInitGraph(linkGraph &G,const Graph &g){
	G.vexes=new VexNode[g.vexNumber];
	G.vexnumber=g.vexNumber;
	for(int i=0;i<g.vexNumber;i++){
		G.vexes[i].firstarc=NULL;
	}
	return 0;
}
//将邻接矩阵存储的图转换为领接表存储的图
void InitGraph(linkGraph &G,const Graph &g,temp &t){
	preInitGraph(G,g);
	for(int i=0;i<t.num;i++){
		int a,b;
		a=t.docu[i].row;b=t.docu[i].col;
		ArcNode *p=new ArcNode();
		p->nextarc=NULL;
		p->adj=b;
		ArcNode *q=G.vexes[a].firstarc;
		if(G.vexes[a].firstarc==NULL)
			G.vexes[a].firstarc=p;
		else{
			while(q->nextarc!=NULL){
				q=q->nextarc;
			}
			q->nextarc=p;
		}
	}
}

int TopologicalSort(linkGraph LG,int Topo[]){
	vector<int>indegree(LG.vexnumber);
	for(int i=0;i<LG.vexnumber;i++) indegree[i]=0;
	for(int i=0;i<LG.vexnumber;i++){
		for(ArcNode *p=LG.vexes[i].firstarc;p!=nullptr;p=p->nextarc)
			indegree[p->adj]++;
	}
	//入度为零的点入栈
	stack<int>s;
	for(int i=0;i<LG.vexnumber;i++){
		if(indegree[i]==0)  s.push(i);
	}

	int i=0;
	while(!s.empty()){
		int j=s.top();s.pop();
		Topo[i++]=j;
		//将Vj邻接点入度减一，减为0的入栈
		for(ArcNode *p=LG.vexes[j].firstarc;p!=nullptr;p=p->nextarc){
			indegree[p->adj]--;
			if(indegree[p->adj]==0)  s.push(p->adj);
		}
	}
	if(i==LG.vexnumber)  return 0;
	else  return 1;
}




//comment

int main(){
	//freopen("/config/workspace/test/test","r",stdin);
	int n,m;
	cin>>n>>m;
	while(n!=0){
		Graph G;
		G.vexNumber=n;
		temp t;
		t.num=m;
		t.docu=new tempNode[m];
		for(int i=0;i<m;i++){
			int a,b;
			cin>>a>>b;
			t.docu[i].row=a-1;
			t.docu[i].col=b-1;
		}
		linkGraph LG;
		InitGraph(LG,G,t);
		int Topo[LG.vexnumber];
		int flag=TopologicalSort(LG,Topo);
		if(flag==0)  cout<<"NO"<<endl;
		else  cout<<"YES"<<endl;
		cin>>n>>m;
	}
	
	return 0;
}

//闲叙的题外话：这周的差点忘记发了哈哈哈