/* ID: espr1t TASK: KEYWORDS: */ #include #include #include #include #include using namespace std; FILE* in = stdin; FILE* out = stdout; // Tarjan's Algorithm // Algorithm for finding strongly connected components in a directed graph // Constructor accepts as arguments // -- integer n: the number of nodes // -- array vert: n vectors of children for each node // Function execute() returns // -- vector < vector >: the strongly connected components // Additional switch for using recursive or iterative algorithm // Default is iterative, and is preferable in order to avoid stack overflows // Implementation by Alexander 'espr1t' Georgiev, February 2009 // Original pseudocode of the implementation is taken from www.wikipedia.org #include #include using namespace std; class Tarjan { private: struct TarjanInfo { int visited; int index, lowIndex; }; // End of struct Tarjan Info struct TarjanState { int node, after; vector check; TarjanState(int node_ = 0, int after_ = 0) {node = node_; after = after_;} }; // End of struct Tarjan State bool USE_RECURSIVE_IMPLEMENTATION; int numNodes; // Number of Nodes vector < vector > v; // Adjecency lists int nextNum; int* inStack; stack s; TarjanInfo* nodeInfo; vector < vector > components; // Normal recursion void recursiveTarjan(int node) { s.push(node); inStack[node] = 1; nodeInfo[node].visited = 1; nodeInfo[node].index = nodeInfo[node].lowIndex = nextNum++; for (int i=0; i<(int)v[node].size(); i++) { if (!nodeInfo[v[node][i]].visited || inStack[v[node][i]]) { if (!nodeInfo[v[node][i]].visited) recursiveTarjan(v[node][i]); nodeInfo[node].lowIndex = min(nodeInfo[node].lowIndex, nodeInfo[v[node][i]].lowIndex); } } if (nodeInfo[node].index == nodeInfo[node].lowIndex) { vector ins; bool flag = false; while (!flag) { ins.push_back(s.top()); flag = (s.top() == node); inStack[s.top()] = 0; s.pop(); } components.push_back(ins); } } // Iterative recursion void iterativeTarjan(int start) { TarjanState cur, next; stack q; q.push(TarjanState(start)); while (!q.empty()) { cur = q.top(); q.pop(); if (!cur.after && nodeInfo[cur.node].visited) continue; if (!cur.after) { s.push(cur.node); inStack[cur.node] = 1; nodeInfo[cur.node].visited = 1; nodeInfo[cur.node].index = nodeInfo[cur.node].lowIndex = nextNum++; vector check; for (int i=0; i<(int)v[cur.node].size(); i++) { if (!nodeInfo[v[cur.node][i]].visited || inStack[v[cur.node][i]]) { if (!nodeInfo[v[cur.node][i]].visited) check.push_back(v[cur.node][i]); else nodeInfo[cur.node].lowIndex = min(nodeInfo[cur.node].lowIndex, nodeInfo[v[cur.node][i]].lowIndex); } } next.node = cur.node; next.after = 1; next.check = check; q.push(next); for (int i=0; i<(int)check.size(); i++) q.push(TarjanState(check[i])); } else { for (int i=0; i< (int)cur.check.size(); i++) { nodeInfo[cur.node].lowIndex = min(nodeInfo[cur.node].lowIndex, nodeInfo[cur.check[i]].lowIndex); } if (nodeInfo[cur.node].index == nodeInfo[cur.node].lowIndex) { vector ins; bool flag = false; while (!flag) { ins.push_back(s.top()); flag = (s.top() == cur.node); inStack[s.top()] = 0; s.pop(); } components.push_back(ins); } } } } public: // Constructor // n is the number of nodes, vert[i] is a vector of children for node i Tarjan(int n, vector * vert, bool recursive = false) { numNodes = n; inStack = new int[n]; nodeInfo = new TarjanInfo[n]; v.resize(n); for (int i=0; i > execute() { nextNum = 1; components.clear(); while (!s.empty()) s.pop(); memset(inStack, 0, sizeof(*inStack)); for (int i=0; i v[MAX]; int main(void) { in = fopen("tourism.in", "rt"); out = fopen("tourism.out", "wt"); fscanf(in, "%d %d", &n, &m); for (int i = 0; i < m; i++) { int node1, node2; fscanf(in, "%d %d", &node1, &node2); node1--, node2--; v[node1].push_back(node2); if (node1 == node2) self[node1] = true; } Tarjan tarjan(n, v); vector < vector > comps = tarjan.execute(); vector ans; for (int i = 0; i < (int)comps.size(); i++) { vector & comp = comps[i]; if ((int)comp.size() == 1) { if (self[comp[0]]) { ans.push_back(comp[0]); } } else { for (int c = 0; c < (int)comp.size(); c++) ans.push_back(comp[c]); } } sort(ans.begin(), ans.end()); for (int i = 0; i < (int)ans.size(); i++) fprintf(out, "%d\n", ans[i] + 1); return 0; }