Pagini recente » Cod sursa (job #1730671) | Cod sursa (job #796830) | Cod sursa (job #1534261) | Cod sursa (job #2394028) | Cod sursa (job #1869386)
#include <iostream>
#include <vector>
#include <bitset>
#define maxN 100100
using namespace std;
//ifstream fin("ctc.in");
//ofstream fout("ctc.out");
vector <int> a[maxN], aTranspus[maxN], s[maxN], v;
int transpus[maxN], sol=0, k=0;
bitset <maxN> viz;
void dfs(int nod){
viz[nod]=1;
for(int i=0; i<a[nod].size(); i++)
if(!viz[a[nod][i]]) dfs(a[nod][i]);
k++;
transpus[nod]=k;
}
void dfsTranspus(int nod){
s[sol].push_back(nod);
viz[nod]=1;
for(int i=0; i<aTranspus[nod].size(); i++)
if(!viz[aTranspus[nod][i]]) dfsTranspus(aTranspus[nod][i]);
}
int main(){
int n, m, x, y;
cin>>n>>m;
for(int i=1; i<=m; i++){
cin>>x>>y;
a[x].push_back(y);
aTranspus[y].push_back(x);
}
for(int i=1; i<=n; i++)
if(!viz[i]) dfs(i);
for(int i=1; i<=n; i++) v.push_back(i);
viz.reset();
for(int i=0; i<n; ++i)
if(!viz[v[i]]){ sol++; dfsTranspus(v[i]); }
cout<<sol<<"\n"; ///afisarea numarului de solutii
for(int i=1; i<=sol; i++){
for(int j=0; j<s[i].size(); j++){
cout<<s[i][j]<<" ";
}
cout<<endl;
}
return 0;
}