Pagini recente » Cod sursa (job #2661057) | Cod sursa (job #1381073) | Cod sursa (job #501465) | Cod sursa (job #663047) | Cod sursa (job #2055362)
#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=1;i<=n;++i)
if(!vis[i]){
++k;
DFS2(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();
}