Cod sursa(job #2083411)

Utilizator MotoAMotoi Alexandru MotoA Data 7 decembrie 2017 18:04:35
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <iostream>
#include <fstream>
using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");
int n,m,post[100001],nr,nrc;
bool viz[100001];
struct nod {
    int val;
    nod *next;
};
nod *v[100001],*vt[100001],*cc[100001];

void add_nod(nod *&cap,int val) {
    nod *p=new nod;
    p->val=val;
    p->next=cap;
    cap=p;
}
void citire_graf() {
    f>>n>>m;
    int x,y;
    for(int i=1; i<=m; i++) {
        f>>x>>y;
        add_nod(v[x],y);
        add_nod(vt[y],x);
    }
}

void DFS(int i) {
    viz[i]=1;
    for(nod *p=v[i];p!=NULL;p=p->next)
        if(!viz[p->val])
            DFS(p->val);
    post[++nr]=i;
}

void DFSt(int i) {
    viz[i]=0;
    add_nod(cc[nrc],i);
    for(nod *p=vt[i];p!=NULL;p=p->next)
        if(viz[p->val])
            DFSt(p->val);
}

void comp_con() {
    for(int i=1;i<=n;i++)
        if(viz[i]==0)
            DFS(i);
    for(int i=n;i>0;i--)
        if(viz[post[i]]==1) {
            nrc++;
            DFSt(post[i]);
        }
}
void afisare() {
    g<<nrc<<'\n';
    for(int i=1;i<=nrc;i++) {
        for(nod *p=cc[i];p!=NULL;p=p->next)
            g<<p->val<<' ';
        g<<'\n';
    }
}
int main() {
    citire_graf();
    comp_con();
    afisare();
    return 0;
}