Cod sursa(job #1894834)

Utilizator Marius7122FMI Ciltea Marian Marius7122 Data 27 februarie 2017 16:35:20
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <stdio.h>
#include <vector>
#define N 100005
using namespace std;

vector<int> g[N],gt[N],cc[N];       ///graf, graf transpus, componente conexe
int n,m,i,j,a,b,nrcc;
int ord[N];
bool viz[N];

void sorttop(int x)     ///sortare topologica
{
    int i;

    viz[x]=true;

    for(i=0;i<g[x].size();i++)
        if(!viz[g[x][i]])
            sorttop(g[x][i]);

    ord[++ord[0]]=x;
}

void dfs(int x)
{
    int i;

    //printf("%d %d\n",nrcc,x);

    cc[nrcc].push_back(x);
    viz[x]=true;

    for(i=0;i<gt[x].size();i++)
        if(!viz[gt[x][i]])
            dfs(gt[x][i]);
}

int main()
{
    FILE *f1,*f2;
    f1=fopen("ctc.in","r");
    f2=fopen("ctc.out","w");

    fscanf(f1,"%d%d",&n,&m);
    for(i=0;i<m;i++)
    {
        fscanf(f1,"%d%d",&a,&b);
        g[a].push_back(b);
        gt[b].push_back(a);
    }

    for(i=1;i<=n;i++)
        if(!viz[i])
            sorttop(i);
    //for(i=1;i<=ord[0];i++)
        //printf("%d ",ord[i]);

    for(i=1;i<=n;i++)
        viz[i]=false;

    for(i=ord[0];i>0;i--)
        if(!viz[ord[i]])
        {
            //printf("%d ",ord[i]);
            nrcc++;
            dfs(ord[i]);
        }

    fprintf(f2,"%d\n",nrcc);
    for(i=1;i<=nrcc;i++)
    {
        for(j=0;j<cc[i].size();j++)
            fprintf(f2,"%d ",cc[i][j]);
        fprintf(f2,"\n");
    }

    return 0;
}