Cod sursa(job #2530790)

Utilizator stefanpiturStefan Alexandru Pitur stefanpitur Data 25 ianuarie 2020 12:23:55
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <iostream>
#include <cstdio>
using namespace std;
const int mmax = 200000;
const int nmax = 100000;

int nr,ctc;
int lst[nmax], lst_inv[nmax];
int urm[mmax], urm_inv[mmax];
int vf[mmax], vf_inv[mmax];
bool visited[nmax];
int visited_inv[nmax];
int top[nmax];

void adauga(int x, int y){
    nr++;
    vf[nr] = y;
    urm[nr] = lst[x];
    lst[x] = nr;

    vf_inv[nr] = x;
    urm_inv[nr] = lst_inv[y];
    lst_inv[y] = nr;
}

void dfs(int node){
    visited[node] = true;
    for(int p=lst[node]; p!=0; p=urm[p]){
        int next = vf[p];
        if(!visited[next])
            dfs(next);
    }
    top[++nr] = node;
}

void dfs_inv(int node){
    visited_inv[node] = ctc;
    for(int p=lst_inv[node]; p!=0; p=urm_inv[p]){
        int next = vf_inv[p];
        if(visited_inv[next] == 0)
            dfs_inv(next);
    }
}

int main()
{
    FILE *fin, *fout;
    int n,m,i,x,y;
    fin = fopen("ctc.in","r");
    fout = fopen("ctc.out","w");
    fscanf(fin,"%d %d",&n,&m);
    for(i=0; i<m; i++){
        fscanf(fin,"%d %d",&x,&y);
        adauga(x,y);
    }
    nr = 0;
    for(i=1; i<=n; i++)
        if(!visited[i])
            dfs(i);
    ctc = 0;
    for(i=nr; i>0; i--)
        if(!visited_inv[top[i]]){
            ctc++;
            nr = 0;
            dfs_inv(top[i]);
        }
    fprintf(fout,"%d\n",ctc);
    for(i=1; i<=ctc; i++){
        for(int j=1; j<=n; j++)
            if(visited_inv[j] == i)
                fprintf(fout,"%d ",j);
        fprintf(fout,"\n");
    }
    fclose(fin);
    fclose(fout);
    return 0;
}