Pagini recente » Cod sursa (job #81314) | Cod sursa (job #1249944) | Cod sursa (job #180568) | Cod sursa (job #318056) | Cod sursa (job #2186239)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5;
vector < vector < int > > scc;
vector < int > g[MAXN + 1], gt[MAXN + 1], stk;
int seen[MAXN + 1];
void regular_dfs(int node) {
seen[node] = 1;
for (auto it : g[node])
if (seen[it] == 0)
regular_dfs(it);
stk.push_back(node);
}
void reverse_dfs(int node, vector < int >& comp) {
seen[node] = 0;
comp.push_back(node);
for (auto it : gt[node])
if (seen[it])
reverse_dfs(it, comp);
}
int main()
{
int n, m;
ifstream fin("ctc.in");
fin >> n >> m;
for (int i = 0; i < m; ++i) {
int x, y;
fin >> x >> y;
g[x].push_back(y);
gt[y].push_back(x);
}
fin.close();
for (int i = 1; i <= n; ++i)
if (seen[i] == 0)
regular_dfs(i);
while (stk.empty() == false) {
if (seen[stk.back()]) {
vector < int > comp;
reverse_dfs(stk.back(), comp);
scc.push_back(comp);
}
stk.pop_back();
}
ofstream fout("ctc.out");
fout << scc.size() << '\n';
for (auto comp : scc) {
for (auto it : comp)
fout << it << " ";
fout << '\n';
}
fout.close();
return 0;
}