Pagini recente » Cod sursa (job #2881960) | Cod sursa (job #2173226) | Cod sursa (job #2095558) | Cod sursa (job #392109) | Cod sursa (job #2755900)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1e5 + 5;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<int> adj[NMAX];
vector<vector<int>> sccs;
int found[NMAX];
int low[NMAX];
stack<int> node_st;
bool in_st[NMAX];
void dfs(int node, int p, int& tmp) {
found[node] = low[node] = ++tmp;
in_st[node] = true;
node_st.push(node);
for (auto neigh : adj[node]) {
if (found[neigh]) {
if (in_st[neigh]) {
// neigh is not in another SCC
low[node] = min(low[node], found[neigh]);
}
continue;
}
dfs(neigh, node, tmp);
low[node] = min(low[node], low[neigh]);
}
if (low[node] == found[node]) {
// node - root of SCC
int curr;
vector<int> new_scc;
do {
curr = node_st.top();
node_st.pop();
in_st[curr] = false;
new_scc.push_back(curr);
} while (curr != node);
sccs.push_back(new_scc);
}
}
int main() {
int N, M;
fin >> N >> M;
int i, x, y;
for (i = 1; i <= M; ++i) {
fin >> x >> y;
adj[x].push_back(y);
}
int tmp = 0;
for (i = 1; i <= N; ++i) {
if (!found[i]) {
dfs(i, i, tmp);
}
}
fout << sccs.size() << "\n";
for (auto scc : sccs) {
for (auto node : scc) {
fout << node << " ";
}
fout << "\n";
}
return 0;
}