Pagini recente » Cod sursa (job #2830859) | Cod sursa (job #3004770) | Cod sursa (job #1563424) | Cod sursa (job #424695) | Cod sursa (job #3243542)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
vector<vector<int>> G;
vector<int> num, lowest;
vector<bool> onStack;
stack<int> s;
vector<vector<int>> sccs;
int index = 0;
void tarjanDFS(int v) {
num[v] = lowest[v] = index++;
s.push(v);
onStack[v] = true;
for (int u : G[v]) {
if (num[u] == -1) {
tarjanDFS(u);
lowest[v] = min(lowest[v], lowest[u]);
} else if (onStack[u]) {
lowest[v] = min(lowest[v], num[u]);
}
}
if (lowest[v] == num[v]) {
vector<int> component;
int w;
do {
w = s.top();
s.pop();
onStack[w] = false;
component.push_back(w);
} while (w != v);
sccs.push_back(component);
}
}
int main() {
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int N, M;
fin >> N >> M;
G.resize(N);
num.assign(N, -1);
lowest.assign(N, -1);
onStack.assign(N, false);
for (int i = 0; i < M; ++i) {
int x, y;
fin >> x >> y;
--x; --y;
G[x].push_back(y);
}
for (int v = 0; v < N; ++v) {
if (num[v] == -1) {
tarjanDFS(v);
}
}
// Write output
fout << sccs.size() << endl;
for (const vector<int>& scc : sccs) {
for (int v : scc) {
fout << v + 1 << " ";
}
fout << endl;
}
return 0;
}