Pagini recente » Borderou de evaluare (job #1570086) | Cod sursa (job #459263) | Cod sursa (job #1730421) | Cod sursa (job #182765) | Cod sursa (job #3216142)
#include <bits/stdc++.h>
using namespace std;
vector<int>S,G[100001],GT[100001];
int f[100001],f2[100001],cnt=0,n,m;
set<int>lista[100001];
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int comp[100001],f3[100001];
void dfs(int nod){
f[nod]=1;
for(auto x : G[nod])
if(!f[x])
dfs(x);
S.push_back(nod);
}
void dfs2(int nod){
f2[nod]=1;
lista[cnt].insert(nod);
comp[nod]=cnt;
for(auto x : GT[nod])
if(!f2[x])
dfs2(x);
}
int main(){
fin>>n>>m;
while(m--){
int x,y; fin>>x>>y;
G[x].push_back(y);
GT[y].push_back(x);
}
for(int i=1;i<=n;i++)
if(!f[i])
dfs(i);
for(vector<int> :: reverse_iterator it= S.rbegin(); it!=S.rend();it++)
if(!f2[*it]){
cnt++;
dfs2(*it);
}
fout<<cnt<<'\n';
for(int i=1;i<=n;i++)
if(!f3[comp[i]]){
/// componenta lui i nu a fost afisata
f3[comp[i]]=1;
for(auto x : lista[comp[i]])
fout<<x<<" ";
fout<<'\n';
}
return 0;
}