Cod sursa(job #1514679)

Utilizator Emy1337Micu Emerson Emy1337 Data 31 octombrie 2015 13:57:51
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#include <stdio.h>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
FILE *fin, *fout;

int n,m,nrtc,VIZ[100001];
vector < int > G[100001];
vector < int > T[100001];
vector < int > A[100001];
stack < int > stiva;

void DFS1(int nod)
{
    vector < int > :: iterator it;
    VIZ[nod]=1;
    for(it=G[nod].begin(); it!=G[nod].end(); it++)
    {
        if(VIZ[*it]==0)
        {
            DFS1(*it);
        }
    }
    stiva.push(nod);
}

void DFS2(int nod)
{
    vector < int > :: iterator it;

    VIZ[nod]=nrtc;
    A[nrtc].push_back(nod);
    for(it=T[nod].begin(); it!=T[nod].end(); it++)
    {
        if(VIZ[*it]==0)
        {
            DFS2(*it);
        }
    }
}


int main()
{

    fin=fopen("ctc.in","r");
    fout=fopen("ctc.out","w");

    fscanf(fin,"%d%d",&n,&m);
    for(int i=1; i<=m; i++)
    {
        int x,y;
        fscanf(fin,"%d%d",&x,&y);
        G[x].push_back(y);
        T[y].push_back(x);
    }

    //le bagam toate in stiva cu dfs
    for(int i=1; i<=n; i++)
    {
        if(VIZ[i]==0)
        {
            DFS1(i);
        }
    }
    //resetam viz
    fill(VIZ+1,VIZ+n+1,0);

    //parcurgem stiva si facem dfs pe graficul transpus
    while(!stiva.empty())
    {

        if(VIZ[stiva.top()]==0)
        {
            nrtc++;
            DFS2(stiva.top());
        }
        stiva.pop();
    }

    vector < int > :: iterator it;

    fprintf(fout,"%d\n",nrtc);
    for(int i=1;i<=nrtc;i++){
        for(it=A[i].begin();it!=A[i].end();it++){
            fprintf(fout,"%d ",*it);
        }
        fprintf(fout,"\n");
    }





}