Cod sursa(job #1490498)

Utilizator tudormaximTudor Maxim tudormaxim Data 23 septembrie 2015 17:37:20
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <bits/stdc++.h>
using namespace std;
const int nmax = 100005;
vector <int> g[nmax], gt[nmax], ctc[nmax];
stack <int> st;
int n, m, nr;
bool viz[nmax];

void dfs1(int nod)
{
    viz[nod]=true;
    for(int i=0; i<g[nod].size(); i++)
        if(viz[g[nod][i]]==false) dfs1(g[nod][i]);
    st.push(nod);
}

void dfs2(int nod)
{
    viz[nod]=true;
    ctc[nr].push_back(nod);
    for(int i=0; i<gt[nod].size(); i++)
        if(viz[gt[nod][i]]==false) dfs2(gt[nod][i]);
}

int main()
{
    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);
    int i, j, x, y;
    scanf("%d %d", &n, &m);
    for(i=1; i<=m; i++)
    {
        scanf("%d %d", &x, &y);
        g[x].push_back(y);
        gt[y].push_back(x);
    }
    for(i=1; i<=n; i++)
        if(viz[i]==false) dfs1(i);
    memset(viz, 0, n+1);
    while(!st.empty())
    {
        if(viz[st.top()]==false)
        {
            nr++;
            dfs2(st.top());
        }
        st.pop();
    }

    printf("%d\n", nr);
    for(i=1; i<=nr; i++)
    {
        for(j=0; j<ctc[i].size(); j++)
            printf("%d ", ctc[i][j]);
        printf("\n");
    }
    return 0;
}