Cod sursa(job #1913736)

Utilizator gapdanPopescu George gapdan Data 8 martie 2017 13:51:15
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <cstdio>
#include <vector>
#include <set>
#include <cstring>
#define NMAX 100005

using namespace std;

int n,m,k,x,y,nrcmp;
vector<int>v[NMAX];
vector<int>v1[NMAX];
set<int>s[NMAX];
int viz[NMAX],vec[NMAX];

void DFS(int nod){
    viz[nod]=1;
    s[nrcmp].insert(nod);
    for(int i=0;i<v1[nod].size();++i)
    {
        if(viz[v1[nod][i]]== 0){
            DFS(v1[nod][i]);
        }
    }
}

void sortaret(int nod)
{
    viz[nod]=1;
    for(int i=0;i<v[nod].size();++i){
        if(viz[v[nod][i]] == 0){
            sortaret(v[nod][i]);
        }
    }
    ++k;
    vec[k]=nod;
}

int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v1[y].push_back(x);
    }
    for(int i=1;i<=n;++i)
    {
        if(viz[i] == 0) sortaret(i);
    }
    memset(viz,0,sizeof(viz));
    for(int i=n;i>=1;--i)
    {
        if(viz[vec[i]] == 0){
            ++nrcmp;
            DFS(vec[i]);
        }
    }
    printf("%d\n",nrcmp);
    for(int i=1;i<=nrcmp;++i)
    {
        set<int>::iterator it;
        for(it=s[i].begin();it!=s[i].end();++it)
            printf("%d ",*it);
        printf("\n");
    }
    return 0;
}