Pagini recente » Cod sursa (job #2313535) | Cod sursa (job #908178) | Cod sursa (job #694819) | Cod sursa (job #1853375) | Cod sursa (job #2942179)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
vector <vector<int>> v, vrev, scc;
vector <int> kosaraju;
const int NMAX = 100005;
int vis[NMAX], visrev[NMAX];
void dfs(int u)
{
vis[u] = 1;
for(auto it: v[u])
if(!vis[it])
dfs(it);
kosaraju.push_back(u);
}
void dfsrev(int u)
{
scc.back().push_back(u);
visrev[u] = 1;
for(auto it: vrev[u])
if(!visrev[it])
dfsrev(it);
}
void Kosaraju(int n)
{
int i;
for(i = 1; i <= n; i++)
if(!vis[i])
dfs(i);
reverse(kosaraju.begin(), kosaraju.end());
for(auto it: kosaraju)
{
if(!visrev[it])
{
scc.push_back({});
dfsrev(it);
}
}
}
int main()
{
int n, m, i, a, b;
cin >> n >> m;
v.resize(n + 1);
vrev.resize(n + 1);
for(i = 1; i <= m; i++)
{
cin >> a >> b;
v[a].push_back(b);
vrev[b].push_back(a);
}
Kosaraju(n);
cout << scc.size() << '\n';
for(i = 0; i < scc.size(); i++)
{
for(auto it: scc[i])
cout << it << ' ';
cout << '\n';
}
return 0;
}