Cod sursa(job #2013640)

Utilizator valorosu_300Cristian Gherman valorosu_300 Data 21 august 2017 22:47:37
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
#include <fstream>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
const int N = 100005;
int dep[N], low[N], st[N], depth, ls, ctc;
bool in_stack[N];
struct nod{
    int nr;
    nod *urm;
}*v[N];
struct lista{
    int val;
    lista *next;
}*l[N];
void adaug_nod(int x, int y){
    nod *nou = new nod;
    nou->nr = y;
    nou->urm = v[x];
    v[x] = nou;
}
void adaug_lista(int x, int y){
    lista *p = new lista;
    p->val = y;
    p->next = l[x];
    l[x] = p;
}
void push_stack(int val, int &ls){
    st[++ls] = val;
    in_stack[val] = true;
}
void new_ctc(int ns, int &ls){
    ctc++;
    do{
        adaug_lista(ctc,st[ls]);
        in_stack[st[ls]] = false;
    }while(st[ls--] != ns);
}
void tarjan(int ns, int &l){
    int nbr;
    nod *q = v[ns];
    low[ns] = dep[ns] = ++depth;
    push_stack(ns,ls);
    while(q){
        nbr = q->nr;
        if(dep[nbr] == 0){
            tarjan(nbr,l);
            low[ns] = min(low[ns], low[nbr]);
        }
        else if(in_stack[nbr])
            low[ns] = min(low[ns], low[nbr]);
        q = q->urm;
    }
    if(dep[ns] == low[ns])
        new_ctc(ns,ls);
}
void print(int n){
    lista *r = new lista;
    out<<n<<"\n";
    for(int i=1;i<=n;i++){
        r = l[i];
        while(r){
            out<<r->val<<" ";
            r = r->next;
        }
        out<<"\n";
    }
}
int main()
{
    int n,m,x,y;
    in>>n>>m;
    for(int i=1;i<=m;i++){
        in>>x>>y;
        adaug_nod(x,y);
    }
    in.close();
    for(int i=1;i<=n;i++)
        if(dep[i] == 0)
            tarjan(i,ls);
    print(ctc);
    out.close();
    return 0;
}