Cod sursa(job #1107096)

Utilizator oprea1si2si3Oprea Sebastian oprea1si2si3 Data 13 februarie 2014 17:12:30
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
#include<fstream>
#include<vector>
#include<iostream>
using namespace std;

int N,M,index[100100],viz[100100],link[100100],sol[100100],nr,pozsol=1,nrsolutii;
vector <int> v[100100],Stack;

void citire() {

    ifstream in("ctc.in");
    int i,x,y;
    in>>N>>M;
    for(i=1;i<=M;i++) {
        in>>x>>y;
        v[x].push_back(y);
    }
    in.close();

}

void dfs(int nod) {

    int vecin,i;
    viz[nod]=1;
    index[nod]=nr;
    link[nod]=nr;
    nr++;
    Stack.push_back(nod);
    for(i=0;i<v[nod].size();i++){
        vecin=v[nod][i];
        if(!index[vecin]){
            dfs(vecin);
            if(link[nod]>link[vecin])
                link[nod]=link[vecin];
        }
        else
            if(viz[vecin])
                if(link[nod]>link[vecin])
                    link[nod]=link[vecin];
    }
    if(link[nod]==index[nod]) {
        sol[pozsol]=Stack.back();
        viz[sol[pozsol]]=0;
        pozsol++;
        while(Stack.back()!=nod){
            Stack.pop_back();
            sol[pozsol]=Stack.back();
            viz[sol[pozsol]]=0;
            pozsol++;
        }
        Stack.pop_back();
        pozsol++;
        nrsolutii++;
    }
}

void solve() {

    int i;
    nr=1;
    for(i=1;i<=N;i++)
        if(!index[i])
            dfs(i);

}

void afisare() {

    ofstream out("ctc.out");
    int i;
    out<<nrsolutii<<'\n';
    for(i=1;i<=pozsol-1;i++)
        if(sol[i]==0)
            out<<'\n';
        else
            out<<sol[i]<<' ';
    out.close();

}

int main () {

    citire();
    solve();
    afisare();
    return 0;

}