Cod sursa(job #902586)

Utilizator andreas_mihAndreas Mihaloianis andreas_mih Data 1 martie 2013 15:16:34
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.86 kb
#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);
        }
    }
}