Cod sursa(job #1016964)

Utilizator andreiiiiPopa Andrei andreiiii Data 26 octombrie 2013 23:38:38
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <cstdio>
#include <cstring>
#include <vector>
#define N 100005
using namespace std;

struct graf
{
    int n;
    graf *next;
};

graf *g[N], *gt[N];
int v[N], s[N];
vector <int> sol[N];
int n, k;

void dfs(int x)
{
    graf *p;
    v[x]=1;
    for(p=g[x];p;p=p->next)
    {
        if(!v[p->n]) dfs(p->n);
    }
    s[++s[0]]=x;
}

void dfs2(int x)
{
    graf *p;
    v[x]=1;
    sol[k].push_back(x);
    for(p=gt[x];p;p=p->next)
    {
        if(!v[p->n]) dfs2(p->n);
    }
}

inline void gadd(graf *g[], int x, int y)
{
    graf *p=new graf;
    p->n=y;
    p->next=g[x];
    g[x]=p;
}

int main()
{
    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);
    int i, m, x, y;
    vector <int>::iterator it;
    scanf("%d%d", &n, &m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d", &x, &y);
        gadd(g, x, y);
        gadd(gt, y, x);
    }
    for(i=1;i<=n;i++)
    {
        if(!v[i])
        {
            dfs(i);
        }
    }
    memset(v, 0, sizeof(v));
    for(i=n;i;i--)
    {
        if(!v[s[i]])
        {
            k++;
            dfs2(s[i]);
        }
    }
    printf("%d\n", k);
    for(i=1;i<=k;i++)
    {
        for(it=sol[i].begin();it!=sol[i].end();it++)
        {
            printf("%d ", *it);
        }
        printf("\n");
    }
}