Cod sursa(job #1547699)

Utilizator netedu_andreiFII Andrei Netedu netedu_andrei Data 9 decembrie 2015 19:18:38
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <stdio.h>
#include <vector>
#include <stack>
#define maxn 100005

using namespace std;

vector <int> a[maxn],atr[maxn],cc[maxn];
stack <int> s;

bool viz[maxn];
int n,m;

void dfs(int nod, bool (&viz)[maxn])
{
    viz[nod]=1;
    unsigned int i;
    for(i=0; i<a[nod].size(); i++)
        if(viz[a[nod][i]] == 0) dfs(a[nod][i], viz);
    s.push(nod);
}

void dfs2(int nod, bool (&viz)[maxn], int &nrc)
{
    viz[nod]=0;
    unsigned int i;
    for(i=0; i<atr[nod].size(); i++)
        if(viz[atr[nod][i]] == 1) dfs2(atr[nod][i], viz, nrc);
    cc[nrc].push_back(nod);
}
int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    scanf("%d %d",&n,&m);
    int i,x,y;
    for(i=0; i<m; i++)
    {
        scanf("%d %d",&x,&y);
        a[x].push_back(y);
        atr[y].push_back(x);
    }

    for(i=1; i<=n; i++)
        if(viz[i] == 0)
            dfs(i, viz);

    int nrc = 0;

    while(!s.empty())
    {
        x = s.top();
        s.pop();
        if (viz[x] != 0)
        {
            dfs2(x, viz, nrc);
            nrc++;
        }
    }
    printf("%d\n",nrc);
    for(i=0; i<nrc; i++)
    {
        unsigned int j;
        for(j=0; j<cc[i].size(); j++)
            printf("%d ",cc[i][j]);
        printf("\n");
    }

    return 0;
}