Cod sursa(job #1766164)

Utilizator radu_cebotariRadu Cebotari radu_cebotari Data 27 septembrie 2016 17:16:34
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include<vector>
#include<algorithm>
#include<stdio.h>
using namespace std;
const int NMAX = 100005;

vector<int> G[NMAX],GT[NMAX],ctc[NMAX];
int N,M,post[NMAX],viz[NMAX],cnt;

void dfs(int nod)
{

    viz[nod] = 1;
    for(vector<int>::iterator it = G[nod].begin() ; it != G[nod].end() ; ++it)
        if(!viz[*it])
            dfs(*it);
    post[++cnt] = nod;
}

void dfs2(int nod,int sol)
{

    viz[nod] = 0;
    ctc[sol].push_back(nod);
    for(vector<int>::iterator it = GT[nod].begin() ; it != GT[nod].end() ; ++it)
        if(viz[*it])
            dfs2(*it,sol);
}

bool cmp(vector<int> a,vector<int> b)
{

    if(a[0] < b[0])
        return true;
    return false;
}

int main()
{

    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    int N,M;
    scanf("%d%d",&N,&M);
    int x,y;
    for(int i = 1 ; i <= M ; ++i){

        scanf("%d%d",&x,&y);
        G[x].push_back(y);
        GT[y].push_back(x);
    }
    for(int i = 1 ; i <= N ; ++i)
        if(!viz[i])
            dfs(i);
    int sol = 0;
    for(int i = N ; i >= 1 ; --i)
        if(viz[post[i]]){
            ++sol;
            dfs2(post[i],sol);
        }
    printf("%d\n",sol);
    for(int i = 1 ; i <= sol ; ++i){
        for(vector<int>::iterator it = ctc[i].begin() ; it != ctc[i].end(); ++it)
            printf("%d ",*it);
        printf("\n");
    }
    return 0;
}