Cod sursa(job #2333915)

Utilizator catalina200029Olteanu Catalina catalina200029 Data 2 februarie 2019 09:42:28
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <bits/stdc++.h>
#define NMAX 100005

using namespace std;

vector<int> v[NMAX];
vector<int> v2[NMAX];
vector<int> sol[NMAX];

FILE*f=fopen("ctc.in","r");
FILE*g=fopen("ctc.out","w");

int n,m,x,y,viz[NMAX],st[NMAX],nr,nrctc;

void df(int k) {
    int i;
    viz[k]=1;
    //cout<<k<<' ';
    for (i=0;i<v[k].size();++i)
        if (!viz[v[k][i]]) df(v[k][i]);
    st[++nr]=k;
}

void df2(int k) {
    int i;
    viz[k]=1;
    sol[nrctc].push_back(k);
    for (i=0;i<v2[k].size();++i)
        if (!viz[v2[k][i]]) df2(v2[k][i]);
}

int main() {
    int i,j;
    fscanf(f,"%d%d",&n,&m);
    for (i=1;i<=m;++i) {
        fscanf(f,"%d%d",&x,&y);
        v[x].push_back(y);
        v2[y].push_back(x);
    }
    for (i=1;i<=n;++i)
        if (!viz[i]) df(i);
    memset(viz,0,sizeof(viz));
    for (i=n;i>=1;--i)
        if (!viz[st[i]]) {
            ++nrctc;
            df2(st[i]);
        }
    fprintf(g,"%d\n",nrctc);
    for (i=1;i<=nrctc;++i) {
        for (j=0;j<sol[i].size();j++)
            fprintf(g,"%d ",sol[i][j]);
        fprintf(g,"\n");
    }
    return 0;
}