swust.oj.1076_综合

判断给定有向图是否存在回路(1076)

Time limit(ms): 1000

Memory limit(kb): 10000

判断给定有向图是否存在回路。

Description

第一行为图中顶点的个数n；第二行为途中弧度条数e；
第二行为顶点信息;接着e行为e条弧依附的两个顶点。

Input

该图是否存在回路，是输出yes;，不是输出no。

Output

Sample Input

        no
       

        #include<stdio.h>
#include<algorithm>
#include<math.h>
#include<string.h>
#include<iostream>
using namespace std;
int mp[20][20];
bool vs[20];
bool k;
int n;void init()
{for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){mp[i][j] = 0;}}
}//初始化地图void dfs(int i)
{if (k)return;//剪枝for (int j = 0; j < n; j++){if (!vs[i] && mp[i][j]){vs[i] = true;//一个一个判断dfs(j);vs[i] = false;//下一个时清除上一个标记}else if(mp[i][j]){k = true;}}
}int main()
{int m;while (cin >> n>>m){char a[20];k = false;memset(vs, false, sizeof(vs));for (int i = 0; i < n; i++){cin >> a[i];}init();for (int i = 0; i < m; i++){char ch1, ch2;cin >> ch1 >> ch2;mp[ch1-'A'][ch2-'A'] = 1;}dfs(0);if (k)cout << "yes";else cout << "no";}return 0;
}
        
 
       