Pagini recente » Cod sursa (job #3276983) | Cod sursa (job #236398) | Cod sursa (job #65267) | Cod sursa (job #1836848) | Cod sursa (job #3133906)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
#define PRINT_VECTOR(V) for (int I = 0; I < V.size(); I++) fout << V[I] << " "; fout << "\n";
const int DIM = 1e5 + 1;
vector <int> adj[DIM];
int ids[DIM], low[DIM];
bool onStack[DIM];
stack<int> nodeStack;
vector<vector<int>> scc;
int id;
void dfs(int v);
void tarjanSCC(int V) {
for (int i = 1; i <= V; ++i) { // iterate from 1 to V
if (ids[i] == -1) {
dfs(i);
}
}
}
void dfs(int v) {
ids[v] = low[v] = id++;
nodeStack.push(v);
onStack[v] = true;
for (int neighbor : adj[v]) {
if (ids[neighbor] == -1) {
dfs(neighbor);
}
if (onStack[neighbor]) {
low[v] = min(low[v], low[neighbor]);
}
}
// If v is a root node, pop the stack and print the SCC
if (ids[v] == low[v]) {
vector<int> temp;
while (!nodeStack.empty()) {
int node = nodeStack.top();
nodeStack.pop();
onStack[node] = false;
temp.push_back(node);
if (node == v) {
break;
}
}
scc.push_back(temp);
}
}
int main() {
int V, E;
fin >> V >> E;
for (int i = 0; i < DIM; ++i) {
ids[i] = -1;
low[i] = -1;
}
while (E--) {
int x, y;
fin >> x >> y;
adj[x].push_back(y);
}
tarjanSCC(V);
fout << scc.size() << "\n";
for (auto s : scc) {
PRINT_VECTOR(s);
}
return 0;
}