Pagini recente » Cod sursa (job #1944491) | Cod sursa (job #644623) | Cod sursa (job #2673810) | Cod sursa (job #330380) | Cod sursa (job #2928510)
// Kosaraju's algorithm
#include <bits/stdc++.h>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
const int con = 1e5 + 5;
vector<int> lad[con], rev[con], post, temp, comps[con], comp;
int n, m, a, b, num_comp;
void dfs(int current, int current_comp = -2)
{
if(comp[current] != -1) return;
comp[current] = current_comp;
for (auto nb : lad[current])
{
dfs(nb, current_comp);
}
post.push_back(current);
}
void kosaraju()
{
comp.assign(n+1, -1);
for (int i = 1; i <= n; i++) dfs(i);
for (int i = 1; i <= n; i++)
for (auto j : lad[i]) rev[j].push_back(i);
swap(rev, lad);
reverse(post.begin(), post.end());
comp.assign(n+1, -1);
for (int i = 0; i < n; i++)
if(comp[post[i]] == -1)
{dfs(post[i], num_comp++);}
}
int main()
{
f >> n >> m;
for(int i = 1; i <= m; i ++)
{
f >> a >> b;
lad[a].push_back(b);
}
kosaraju();
cout << num_comp << "\n";
for(int i = 1; i <= n; i++)
comps[comp[i]].push_back(i);
for(int i = 0; i < num_comp; i++)
{
for(auto a:comps[i])
cout << a << " ";
cout << "\n";
}
return 0;
}