|
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 97 98 99 100 101 102 |
#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> #include <cmath> using namespace std; vector<int> ljb[404]; 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; scanf(" %d %d",&n,&m); for (int i = 1; i <= n*m; i++) { ljb[i].clear(); } for (int i = 1; i <= n; i++) { char way = 0; scanf(" %c",&way); if (way == '>') { for (int j = 1; j < m; j++) { ljb[(i-1)*m+j].push_back((i-1)*m+j+1); } }else{ for (int j = m; j > 1; j--) { ljb[(i-1)*m+j].push_back((i-1)*m+j-1); } } } for (int i = 1; i <= m; i++) { char way = 0; scanf(" %c",&way); if (way == '^') { for (int j = n; j > 1; j--) { ljb[(j-1)*m+i].push_back((j-2)*m+i); } }else{ for (int j = 1;j < n; j++) { ljb[(j-1)*m+i].push_back((j)*m+i); } } } dfs(1); for (int i = 0; i < ccs.size(); i++) { if (ccs[i].size() == n*m) { printf("YESn"); return 0; } } printf("NOn"); return 0; return 0; } |
强联通分量的题，建图搞定了就搞定了。关于scc的算法可以翻我的图论标签找一下我写的一篇tarjan算法总结。