|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> using namespace std; vector<int> ljb[10005]; vector<int> ljbt[10005]; bool res[10005]; void dfs(bool t,int currNode){ res[currNode] = true; vector<int> now; if(t) now = ljbt[currNode]; else now = ljb[currNode]; for (int i = 0;i < now.size();i++) { if (res[now[i]]) continue; dfs(t,now[i]); } } int main(){ int n = 0,m = 0; while (scanf(" %d %d",&n,&m) != EOF) { if (n == 0 && m == 0){ break; }else { for (int i = 1;i <= n;i++) { ljb[i].clear(); ljbt[i].clear(); } for (int i = 1;i <= m;i++) { int a = 0,b = 0; scanf(" %d %d",&a,&b); ljb[a].push_back(b); ljbt[b].push_back(a); } bool flag = true; memset(res,0,sizeof(res)); dfs(true,1); for (int i = 1;i <= n;i++) { if(!res[i]){ flag = false; break; } } if(flag){ memset(res,0,sizeof(res)); dfs(false,1); for (int i = 1;i <= n;i++) { if(!res[i]){ flag = false; break; } } } if(flag){ cout << "Yes" << endl; }else{ cout << "No" << endl; } } } return 0; } |
这个问题的类型是有向图强连通，有几种好的固定算法。我会开个小总结的。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> using namespace std; vector<int> ljb[10005]; bool vis[10005]; bool instk[10005]; int dfn[10005]; int low[10005]; int tim = 0; stack<int> stk; vector<vector<int> > ccs; void dfs(int currNode){ vis[currNode] = true; dfn[currNode] = low[currNode] = tim++; stk.push(currNode); instk[currNode] = true; vector<int> now = ljb[currNode]; for (int i = 0;i < now.size(); i++) { if (!vis[now[i]]) { dfs(now[i]); low[currNode] = min(low[currNode],low[now[i]]); }else if (instk[now[i]]) { low[currNode] = min(low[currNode],dfn[now[i]]); } } if (dfn[currNode] == low[currNode]) { int tmp = 0; vector<int> res; while (currNode != tmp) { tmp = stk.top(); res.push_back(tmp); //cout << tmp << "~"; stk.pop(); instk[tmp] = false; } //sort(res.begin(),res.end()); ccs.push_back(res); //cout << endl; } } int main(){ int n = 0,m = 0; while (scanf(" %d %d",&n,&m) != EOF) { if (n == 0 && m == 0){ break; }else { for (int i = 1;i <= n;i++) { ljb[i].clear(); } for (int i = 1;i <= m;i++) { int a= 0,b = 0; scanf(" %d %d",&a,&b); ljb[a].push_back(b); } memset(vis, 0, sizeof(vis)); memset(instk, 0, sizeof(instk)); memset(dfn, 0, sizeof(dfn)); memset(low, 0, sizeof(low)); ccs.clear(); while (!stk.empty()) { stk.pop(); } dfs(1); bool flag = false; for (int i = 0; i < ccs.size(); i++) { if (ccs[i].size() == n) { flag = true; } } if (flag) { cout << "Yes" << endl; }else { cout << "No" << endl; } } } return 0; } |