Cod sursa(job #2590417)

Utilizator GiosinioGeorge Giosan Giosinio Data 27 martie 2020 21:13:43
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <bits/stdc++.h>
#define DIM 100005

using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

struct node{
    int v;
    node *next;
}*L[DIM], *LT[DIM], *cpt[10005];

int N,M,comp;
stack <int> finalizare;
bool parcurs1[DIM];

void add(int x, int y, node *L[]){
    node *p = new node;
    p->v = y; p->next = L[x];
    L[x] = p;
}

void citire(){
    f>>N>>M;
    int x,y;
    for(int i=1; i<=M; i++){
        f>>x>>y;
        add(x,y,L);
        add(y,x,LT);
    }
}

void dfs1(int i, bool parcurs[], node *L[]){
    parcurs1[i] = 1;
    for(node *p = L[i]; p != nullptr; p = p->next)
        if(parcurs[p->v] == 0)
            dfs1(p->v, parcurs, L);
    finalizare.push(i);
}

void dfs2(int i, bool parcurs[], node *L[]){
    parcurs[i] = 1;
    for(node *p = L[i]; p != nullptr; p = p->next)
        if(parcurs[p->v] == 0)
            dfs2(p->v, parcurs, L);
    add(comp,i,cpt);
}

void tareConex(){
    bool parcurs2[DIM];
    while(!finalizare.empty()){
        if(parcurs2[finalizare.top()] == 0){
            dfs2(finalizare.top(), parcurs2, LT);
            comp++;
        }
        finalizare.pop();
    }
    g<<comp<<"\n";
    for(int i=0; i<comp; i++){
        while(cpt[i] != nullptr){
            g<<cpt[i]->v<<" ";
            cpt[i] = cpt[i]->next;
        }
        g<<"\n";
    }
}

int main(){
   citire();
   for(int i=1; i<=N; i++)
        if(parcurs1[i] == 0)
            dfs1(i, parcurs1, L);
   tareConex();
}