Pagini recente » Cod sursa (job #961742) | Cod sursa (job #1654727) | Cod sursa (job #2945333) | Cod sursa (job #2759634) | Cod sursa (job #2055364)
#include<fstream>
#include<bitset>
#include<list>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int NMAX=100005;
list<int>g[NMAX],gt[NMAX],ans[NMAX];
int topo_sort[NMAX],n,m,k;
bitset<NMAX>vis;
void read_data(){
int from,to;
fin>>n>>m;
while(m--){
fin>>from>>to;
g[from].push_back(to);
gt[to].push_back(from);
}
}
void DFS(int node){
vis[node]=true;
list<int>::iterator it;
for(it=g[node].begin();it!=g[node].end();++it)
if(!vis[*it])
DFS(*it);
topo_sort[++k]=node;
}
void topological_sort(){
int i;
for(i=1;i<=n;++i)
if(!vis[i])
DFS(i);
vis.reset();
k=0;
}
void DFS2(int node){
vis[node]=true;
ans[k].push_back(node);
list<int>::iterator it;
for(it=gt[node].begin();it!=gt[node].end();++it)
if(!vis[*it])
DFS2(*it);
}
void kosaraju(){
int i;
for(i=n;i>=1;--i)
if(!vis[topo_sort[i]]){
++k;
DFS2(topo_sort[i]);
}
}
void print(){
int i;
list<int>::iterator it;
fout<<k<<'\n';
for(i=1;i<=k;++i){
for(it=ans[i].begin();it!=ans[i].end();++it)
fout<<*it<<' ';
fout<<'\n';
}
}
int main(){
read_data();
topological_sort();
kosaraju();
print();
}