Pagini recente » Diferente pentru home intre reviziile 336 si 335 | Cod sursa (job #2071982) | Cod sursa (job #2206076) | Cod sursa (job #344972) | Cod sursa (job #574171)
Cod sursa(job #574171)
#include <cstdio>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
#define N 100005
vector<int> Gi[N],Gt[N],G[N];
vector<bool> viz;
stack<int> dr;
void DFI (int x){
viz[x]=true;
for(vector<int>::iterator i=Gi[x].begin();i<Gi[x].end();++i)
if(viz[(*i)]==false)
DFI(*i);
dr.push(x);
}
vector<int> drm;
void DFJ (int x, int v){
drm[x]=v;
for(vector<int>::iterator i=Gt[x].begin();i<Gt[x].end();++i)
if(drm[(*i)]==-1)
DFJ(*i,v);
}
int main ()
{
int n,m;
ifstream in ("ctc.in");
freopen ("ctc.out","w",stdout);
in>>n>>m;
for(;m;--m){
int x,y;
in>>x>>y;
Gi[x].push_back(y);
Gt[y].push_back(x);
}
viz.resize(n+1,false);
for(int i=1;i<=n;++i)
if(viz[i]==false)
DFI(i);
drm.resize(n+1,-1);
int c=0;
for(;!dr.empty();dr.pop())
if(drm[dr.top()]==-1){
DFJ(dr.top(),c);
++c;
}
for(int i=1;i<=n;++i)
G[drm[i]].push_back(i);
printf("%d\n",c);
for(int i=0;i<c;++i){
for(vector<int>::iterator it=G[i].begin();it<G[i].end();++it)
printf("%d ",(*it));
printf("\n");
}
return 0;}