Pagini recente » Cod sursa (job #792302) | Cod sursa (job #828086) | Cod sursa (job #442428) | Cod sursa (job #1609297) | Cod sursa (job #2926456)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<vector<int> >adj;
vector<vector<int> >components;
vector<bool>onStack;
vector<int>idx, lowlink;
stack<int>s;
int currIdx = 1;
void strongConnect(int node) {
idx[node] = lowlink[node] = currIdx;
currIdx++;
s.push(node);
onStack[node] = true;
for(auto vec: adj[node]) {
if(idx[vec] == 0) {
strongConnect(vec);
lowlink[node] = min(lowlink[node], lowlink[vec]);
} else if(onStack[vec]) {
lowlink[node] = min(lowlink[node], idx[vec]);
}
}
if(idx[node] == lowlink[node]) {
vector<int>component;
int currNode;
do {
currNode = s.top();
s.pop();
component.push_back(currNode);
onStack[currNode] = false;
} while(currNode != node);
components.push_back(component);
}
}
int main() {
int n, m, x, y;
fin >> n >> m;
adj.resize(n + 1);
idx.resize(n + 1, 0);
lowlink.resize(n + 1, 0);
onStack.resize(n + 1, false);
for(int i = 0; i < m; i++) {
fin >> x >> y;
adj[x - 1].push_back(y - 1);
}
for(int i = 0; i < n; i++) {
if(idx[i] == 0) {
strongConnect(i);
}
}
fout << components.size() << "\n";
for(auto component: components) {
for(auto node: component) {
fout << node + 1 << " ";
}
fout << "\n";
}
return 0;
}