Pagini recente » Cod sursa (job #1161990) | Cod sursa (job #846785) | Cod sursa (job #2535317) | Cod sursa (job #2292596) | Cod sursa (job #928280)
Cod sursa(job #928280)
#include<cstdio>
#include<vector>
using std::vector;
static vector<int> v[100005], rv[100005], ord, ccomp;
static vector<vector<int> > comps;
static bool seen[100005], rseen[100005];
void dfs (int n)
{
seen[n]=1;
for(vector<int>::iterator it=v[n].begin();it!=v[n].end();it++)
if(!seen[*it])
dfs (*it);
ord.push_back (n);
}
void rdfs (int n)
{
ccomp.push_back (n);
rseen[n]=1;
for(vector<int>::iterator it=rv[n].begin();it!=rv[n].end();it++)
if(!rseen[*it])
rdfs (*it);
}
int main (void)
{
freopen ("ctc.in","r",stdin);
#ifdef INFOARENA
freopen ("ctc.out","w",stdout);
#endif
int n,m;
scanf ("%d%d",&n,&m);
while(m--){
int x,y;
scanf ("%d%d",&x,&y);
v[x].push_back (y);
rv[y].push_back (x);
}
for(int i=1;i<=n;i++)
if(!seen[i])
dfs (i);
while(!ord.empty()){
while(!ord.empty() && rseen[ord.back()])
ord.pop_back();
if(!ord.empty()){
ccomp.clear();
rdfs (ord.back());
comps.push_back (vector<int>(ccomp));
}
}
printf ("%lu\n",comps.size());
for(vector<vector<int> >::iterator it=comps.begin();it!=comps.end();it++){
for(vector<int>::iterator itt=it->begin();itt!=it->end();itt++)
printf ("%d ",*itt);
puts ("");
}
return 0;
}