Pagini recente » Cod sursa (job #1010613) | Cod sursa (job #2591972) | Cod sursa (job #798905) | Cod sursa (job #2205248) | Cod sursa (job #2968904)
#include <bits/stdc++.h>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
vector <vector<int>> v, vrev, ctc;
int n, m;
const int N = 1e5 + 1;
int viz[N + 1], vizrev[N + 1];
vector <int> kosaraju;
void dfs(int x)
{
viz[x] = 1;
for(auto i:v[x])
{
if(!viz[i])
dfs(i);
}
kosaraju.push_back(x);
}
void dfsrev(int x)
{
ctc.back().push_back(x);
vizrev[x] = 1;
for(auto i:vrev[x])
{
if(!vizrev[i])
{
vizrev[i] = 1;
dfsrev(i);
}
}
}
void Kosaraju(int n)
{
for(int i = 1; i <= n; i++)
if(!viz[i])
dfs(i);
reverse(kosaraju.begin(), kosaraju.end());
for(auto i:kosaraju)
{
if(!vizrev[i])
{
ctc.push_back({});
dfsrev(i);
}
}
}
int main()
{
in >> n >> m;
v.resize(n + 1);
vrev.resize(n + 1);
for(int i = 1; i <= m; i++)
{
int x, y;
in >> x >> y;
v[x].push_back(y);
vrev[y].push_back(x);
}
Kosaraju(n);
out << ctc.size() << '\n';
for(int i = 0; i < ctc.size(); i++)
{
for(auto x:ctc[i])
out << x << ' ';
out << '\n';
}
return 0;
}