Cod sursa(job #793835)

Utilizator romircea2010FMI Trifan Mircea Mihai romircea2010 Data 4 octombrie 2012 12:46:25
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.94 kb
#include <fstream>
#include <iostream>
#include <cstdlib>

using namespace std;

int N, M, *a[100010], *at[100010], p[100010], np, viz[100010], c[100010], nrc;

inline void Read()
{
    ifstream f("ctc.in");
    f>>N>>M;
    //ofstream fout("fisier.txt");
    //cout<<M;
    //fout.close();
    int i, x, y;
    for (i=1; i<=N; i++)
    {
        a[i] = (int *)realloc(a[i], sizeof(int));
        a[i][0] = 0;
        at[i] = (int *)realloc(at[i], sizeof(int));
        at[i][0] = 0;
    }
    //cout<<M;
    for (i=1; i<=M; i++)
    {

        f>>x>>y;
        a[x][0]++;
        a[x] = (int *)realloc(a[x], (a[x][0] + 1) * sizeof(int));
        a[x][a[x][0]] = y;
        //cout<<a[x][a[x][0]]<<", ";
        at[y][0]++;
        at[y] = (int *)realloc(at[y], (at[y][0] + 1) * sizeof(int));
        at[y][at[y][0]] = x;
        //cout<<at[y][at[y][0]]<<", ";
    }
    f.close();
}

inline void DFS(int x)
{
    viz[x] = 1;
    for(int i=1; i<=a[x][0]; i++)
        if(!viz[a[x][i]])
            DFS(a[x][i]);
    p[++np] = x;
}

inline void DFST(int x)
{
    viz[x] = 0;
    c[x] = nrc;
    for(int i=1; i<=at[x][0]; i++)
        if(viz[at[x][i]])
            DFST(at[x][i]);
}

inline void Write()
{
    ofstream g("ctc.out");
    g<<nrc<<"\n";
    int i, j, x;
    for (i=1; i<=N; i++)
    {
        if (c[i])
        {
            x = c[i];
            g<<i<<" ";
            c[i] = 0;
            for (j=i+1; j<=N; j++)
                if (c[j] == x)
                    {
                        c[j] = 0;
                        g<<j<<" ";
                    }
            g<<"\n";
        }
    }
    g.close();
}

int main()
{
    Read();
    int i;
    for(i=1; i<=N; i++)
        if(!viz[i])
            DFS(i);
    for(i=N; i; i--)
        if(viz[p[i]])
        {
            nrc++;
            DFST(p[i]);
            //cout<<"da";

        }
    Write();
    return 0;
}