Pagini recente » Cod sursa (job #626200) | Cod sursa (job #2697685) | Cod sursa (job #2091699) | Cod sursa (job #61102) | Cod sursa (job #1314815)
#include<stdio.h>
#include<vector>
using namespace std;
FILE *in,*out;
//definitii
#define pb push_back
//constante
const int Nmax = (int) 1e5+1;
//variabile
int n,m;
int x,y;
int nr, rez;
int postordine[Nmax];
bool viz[Nmax];
vector<int> graf[Nmax];
vector<int> graft[Nmax];
vector<int> answer[Nmax];
//functii
void dfs(int nod);
void dfst(int node);
int main(void)
{
in = fopen("ctc.in","rt");
out = fopen("ctc.out","wt");
fscanf(in,"%d%d",&n, &m);
for(int i=1; i<=m; ++i)
{
fscanf(in,"%d%d",&x,&y);
graf[x].pb(y);
graft[y].pb(x);
}
for(int i=1; i<=n; ++i)
if(!viz[i])
dfs(i);
for(int i=n; i>=1; --i)
if(viz[postordine[i]])
{
dfst(postordine[i]);
rez++;
}
fprintf(out,"%d\n",rez);
for(int i=0; i<rez; ++i)
{
vector<int> :: iterator it, end=answer[i].end();
for(it = answer[i].begin(); it!=end; ++it)
fprintf(out,"%d ",*it);
fprintf(out,"\n");
}
fclose(in);
fclose(out);
return 0;
}
void dfs(int nod)
{
viz[nod] = true;
vector<int> :: iterator it, end = graf[nod].end();
for(it = graf[nod].begin(); it != end; ++it)
if(!viz[*it])
dfs(*it);
postordine[++nr]=nod;
}
void dfst(int node)
{
viz[node] = false;
answer[rez].pb(node);
vector<int> :: iterator it, end=graft[node].end();
for(it = graft[node].begin(); it != end; ++it)
if(viz[*it])
dfst(*it);
}