Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <unordered_set>
- #include <algorithm>
- using namespace std;
- class Capcity {
- private:
- void dfs(vector<vector<int>>& graph, int root, vector<bool>& visited, vector<int>& cache) {
- if (visited[root]) {
- return;
- }
- visited[root] = true;
- for (int x : graph[root]) {
- dfs(graph, x, visited, cache);
- }
- cache.push_back(root);
- }
- public:
- vector<int> kosaraju(vector<vector<int>>& graph, vector<vector<int>>& graphT) {
- int n = graph.size();
- vector<bool> visited(n, false);
- vector<int> dfsCache;
- for (int i = 0; i < n; ++i) {
- dfs(graph, i, visited, dfsCache);
- }
- fill(visited.begin(), visited.end(), false);
- vector<vector<int>> sccNodes;
- for (int i = n - 1; i >= 0; --i) {
- if (visited[dfsCache[i]]) {
- continue;
- }
- vector<int> nodes;
- dfs(graphT, dfsCache[i], visited, nodes);
- sccNodes.push_back(nodes);
- }
- vector<int> sccMap(n);
- int sccN = sccNodes.size();
- vector<int> indegrees(sccN, 0);
- for (int i = 0; i < sccN; ++i) {
- for (int x : sccNodes[i]) {
- sccMap[x] = i;
- }
- }
- vector<unordered_set<int>> sccGraph(sccN);
- for (int i = 0; i < n; ++i) {
- int from = sccMap[i];
- for (int x : graph[i]) {
- int to = sccMap[x];
- if (from != to) {
- sccGraph[from].insert(to);
- }
- }
- }
- for (int i = 0; i < sccN; ++i) {
- for (int x : sccGraph[i]) {
- indegrees[x]++;
- }
- }
- int headNode = -1;
- for (int i = 0; i < sccN; ++i) {
- if (indegrees[i] == 0) {
- if (headNode < 0) {
- headNode = i;
- } else {
- headNode = -1;
- break;
- }
- }
- }
- if (headNode == -1) {
- return vector<int>();
- }
- vector<int>& result = sccNodes[headNode];
- sort(result.begin(), result.end());
- return result;
- }
- };
- int main() {
- int n, m;
- cin >> n >> m;
- vector<vector<int>> graph(n);
- vector<vector<int>> graphT(n);
- for (int i = 0; i < m; ++i) {
- int a, b;
- cin >> a >> b;
- --a;
- --b;
- graph[b].push_back(a);
- graphT[a].push_back(b);
- }
- vector<int> result = Capcity().kosaraju(graph, graphT);
- cout << result.size() << endl;
- if (result.empty()) {
- return 0;
- }
- cout << (result[0] + 1);
- for (int i = 1; i < result.size(); ++i) {
- cout << " " << (result[i] + 1);
- }
- cout << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement