Cod sursa(job #1230722)

Utilizator thewildnathNathan Wildenberg thewildnath Data 19 septembrie 2014 09:41:01
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include<stdio.h>
#include<vector>
#include<string.h>
#include<algorithm>

using namespace std;

#define NMAX 100002

int n, m;
int nr, t[NMAX], numctc, lctc, ct[NMAX], l[NMAX];
bool viz[NMAX];

vector<int>v[NMAX], vinv[NMAX];

void dfs(int nod)
{
    for(int i=0; i<v[nod].size(); ++i)
    {
        int fiu=v[nod][i];

        if(!viz[fiu])
        {
            viz[fiu]=true;

            dfs(fiu);
        }
    }

    t[++nr]=nod;
}

void ctc(int nod)
{
    ct[++lctc]=nod;

    for(int i=0; i<vinv[nod].size(); ++i)
    {
        int fiu=vinv[nod][i];

        if(!viz[fiu])
        {
            viz[fiu]=true;

            ctc(fiu);
        }
    }
}

int main()
{
    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);

    int x, y;

    scanf("%d%d", &n, &m);

    for(int i=1; i<=m; ++i)
    {
        scanf("%d%d", &x, &y);

        v[x].push_back(y);
        vinv[y].push_back(x);
    }

    for(int i=1; i<=n; ++i)
    {
        if(!viz[i])
        {
            viz[i]=true;

            dfs(i);
        }
    }

    memset(viz, 0, sizeof(viz));
    for(int i=n; i>=1; --i)
    {
        if(!viz[t[i]])
        {
            l[++numctc]=lctc+1;

            viz[t[i]]=true;

            ctc(t[i]);
        }
    }
    l[numctc+1]=lctc+1;

    printf("%d\n", numctc);
    for(int i=1; i<=numctc; ++i)
    {
        sort(ct+l[i], ct+l[i+1]);
        for(int j=l[i]; j<l[i+1]; ++j)
            printf("%d ", ct[j]);
        printf("\n");
    }

    return 0;
}