Pagini recente » Cod sursa (job #346643) | Cod sursa (job #1023354) | Cod sursa (job #801539) | Cod sursa (job #671127) | Cod sursa (job #902586)
Cod sursa(job #902586)
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<queue>
#include<utility>
#include<string.h>
#include<stack>
using namespace std;
FILE*in=fopen("ctc.in","r");
FILE*out=fopen("ctc.out","w");
int noduri,muchii;
bool vizitat[100001];
int tata[100001],afisat;
stack <int> v;
vector< int > graf[100001],graf2[100001],rasp[100001];
void parcurgere(int nod);
void parcurgere2(int nod,int start);
int main()
{
fscanf(in,"%d%d",&noduri,&muchii);
for(int i=1;i<=muchii;++i)
{
int data1,data2;
fscanf(in,"%d%d",&data1,&data2);
graf[data1].push_back(data2);
graf2[data2].push_back(data1);
}
for(int i=1;i<=noduri;++i)
if(!vizitat[i])
{
vizitat[i]=true;
parcurgere(i);
}
memset(vizitat,false,sizeof(vizitat));
while(!v.empty())
{
int curent=v.top();
v.pop();
if(vizitat[curent])
continue;
else
{
vizitat[curent]=true;
parcurgere2(curent,curent);
++afisat;
}
}
fprintf(out,"%d\n",afisat);
for(int i=0;i<afisat;++i)
{
for(int j=0;j<(int)rasp[i].size();++j)
fprintf(out,"%d ",rasp[i][j]);
fprintf(out,"\n");
}
fclose(in);
fclose(out);
return 0;
}
void parcurgere(int nod)
{
for(int i=0;i<(int)graf[nod].size();++i)
if(!vizitat[graf[nod][i]])
{
vizitat[graf[nod][i]]=true;
parcurgere(graf[nod][i]);
}
v.push(nod);
}
void parcurgere2(int nod,int start)
{
rasp[afisat].push_back(nod);
for(int i=0;i<(int)graf2[nod].size();++i)
{
if(!vizitat[graf2[nod][i]])
{
vizitat[graf2[nod][i]]=true;
parcurgere2(graf2[nod][i],start);
}
}
}