Pagini recente » Monitorul de evaluare | Cod sursa (job #2950149) | Cod sursa (job #2332549) | Cod sursa (job #1534749) | Cod sursa (job #2796514)
//kosaraju
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int N = 100010;
int viz_1[N],viz_2[N];
vector<int> nxt[N], prv[N], ans[N], top;
int n,m, nr_ans;
void dfs_1(int node){
viz_1[node] = 1;
for(auto it : nxt[node])
if(!viz_1[it])
dfs_1(it);
top.push_back(node);
}
void dfs_2(int node){
viz_2[node] = 1;
ans[nr_ans].push_back(node);
for(auto it:prv[node])
if(!viz_2[it])
dfs_2(it);
}
int main(){
fin>>n>>m;
for(int i=1;i<=m;i++)
{
int x,y;
fin>>x>>y;
nxt[x].push_back(y);
prv[y].push_back(x);
}
for(int i=1;i<=n;i++)
if(!viz_1[i])
dfs_1(i);
reverse(top.begin(),top.end());
for(auto it:top)
if(!viz_2[it])
{
nr_ans++;
dfs_2(it);
}
fout<<nr_ans;
for(const auto &it:ans)
{
for(auto elem:it)
fout<<elem<<" ";
fout<<'\n';
}
return 0;
}