Cod sursa(job #899091)

Utilizator robertgbrrobertgbr robertgbr Data 28 februarie 2013 12:52:12
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 2.12 kb
#include <cstdio>
#include <vector>
#define nlength 100010
using namespace std;
int n,m,t;
vector<int>mylist[nlength];
vector<int>revlist[nlength];
int rev_seen[nlength],f[nlength],ff[nlength];
int my_seen[nlength],leader;
int iii,show[nlength];

void compute_new_nodes()
{
    for(int i=1;i<=n;i++)
    {
        vector<int>::iterator it;
        for(it=revlist[i].begin();it!=revlist[i].end();it++)
        {
            mylist[f[*it]].push_back(f[i]);
        }
    }
}

int dfs_loop_my(int k)
{
    vector<int>::iterator it;
    for(it=mylist[k].begin();it!=mylist[k].end();it++)
    {
        if(!my_seen[*it])
        {
            iii++;
            show[iii]=*it;
            my_seen[*it]=1;
            dfs_loop_my(*it);
        }
    }
}

int dfs_loop_rev(int k)        // compute finishing times
{
    vector<int>::iterator it;
    for(it=revlist[k].begin();it!=revlist[k].end();it++)
    {
        if(!rev_seen[*it])
        {
            rev_seen[*it]=1;
            dfs_loop_rev(*it);
        }
    }
    t++;
    f[k]=t;
    ff[t]=k;
}

void read_data()
{
    FILE *inFile;inFile=fopen("ctc.in","r");
    fscanf(inFile,"%d %d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        fscanf(inFile,"%d %d",&x,&y);
        revlist[y].push_back(x); //graph G-reverse
    }
    fclose(inFile);
}

int main()
{
    FILE *outFile;outFile=fopen("ctc.out","w");
    read_data();
    for(int i=n;i>=1;i--)
    {
        if(!rev_seen[i])
        {
            rev_seen[i]=1;
            dfs_loop_rev(i);
        }
    }
    compute_new_nodes();
    int nr=0;
    for(int i=n;i>=1;i--)
    {
        if(!my_seen[i])
        {
            nr++;
            my_seen[i]=1;
            show[++iii]=i;
            dfs_loop_my(i);
            show[++iii]=-1;
        }
    }
    fprintf(outFile,"%d\n",nr);
    iii=1;
    for(int i=1;i<=nr;i++)
    {
        while(show[iii]!=-1)
        {
            fprintf(outFile,"%d ",ff[show[iii]]);
            iii++;
        }
        iii++;
        fprintf(outFile,"\n");
    }

    fclose(outFile);
    return 0;
}