Pagini recente » Cod sursa (job #411355) | Cod sursa (job #1405007) | Cod sursa (job #2857620) | Cod sursa (job #757133) | Cod sursa (job #1725379)
#include <fstream>
#include <stack>
#include <algorithm>
#include <vector>
#define NMAX 100005
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector<int> G[NMAX],GT[NMAX],ras[NMAX];
int viz[NMAX];
stack<int> s;
int n,m;
void citire(){
f>>n>>m;
int i,x,y;
for(i=1;i<=m;i++){
f>>x>>y;
G[x].push_back(y);
GT[y].push_back(x);
}
}
void DFS(int x){
viz[x]=1;
for(vector<int>::iterator it=G[x].begin();it!=G[x].end();it++)
if(viz[*it]==0)
DFS(*it);
s.push(x);
}
void tranDFS(int x,int nr){
viz[x]=1;
ras[nr].push_back(x);
for(vector<int>::iterator it=GT[x].begin();it!=GT[x].end();it++)
if(viz[*it]==0)
tranDFS(*it,nr);
}
int main(){
citire();
int i;
for(i=1;i<=n;i++){
if(viz[i]==0)
DFS(i);
}
fill(viz+1,viz+1+n,NULL);
int contor=0;
while(!s.empty()){
if(viz[s.top()]==0){
++contor;
tranDFS(s.top(),contor);
}
s.pop();
}
g<<contor<<'\n';
for(i=1;i<=contor;i++){
sort(ras[i].begin(),ras[i].end());
for(vector<int>::iterator it=ras[i].begin();it!=ras[i].end();it++)
g<<*it<<' ';
g<<'\n';
}
return 0;
}