Cod sursa(job #1791671)

Utilizator Kln1000Ciobanu Bogdan Kln1000 Data 29 octombrie 2016 16:51:50
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

struct nod{
int index,lowlink;
bool available=true,stacked=false;
vector <int> vecini;};

int n,m,indexare=0;
vector <int> stack;
vector < vector<int> > solutie;
vector <nod> v(100010);

void citire(){
    int x,y;
    f>>n>>m;
    for (int i=0;i<m;++i)
        f>>x>>y,v[x-1].vecini.push_back(y-1);
}

void unload(int nod){
    int a;
    vector <int> aux;
    do{
        a=stack.back();
        stack.pop_back();
        aux.push_back(a);
        v[a].stacked=false;
    }while (a!=nod);
    solutie.push_back(aux);
}

void dfs(int x){
    v[x].available=false;
    v[x].index=v[x].lowlink=indexare++;
    stack.push_back(x);
    v[x].stacked=true;
    for (unsigned i=0;i<v[x].vecini.size();++i)
        if (v[v[x].vecini[i]].available)
            dfs(v[x].vecini[i]),v[x].lowlink=min(v[x].lowlink,v[v[x].vecini[i]].lowlink);
        else if (v[v[x].vecini[i]].stacked)
            v[x].lowlink=min(v[x].lowlink,v[v[x].vecini[i]].lowlink);
    if (v[x].lowlink==v[x].index)
        unload(x);
}

int main()
{
    citire();
    for (int i=0;i<n;++i)
        if (v[i].available)
        dfs(i);
    t<<solutie.size()<<'\n';
    for(unsigned i=0;i<solutie.size();++i){
        for (unsigned j=0;j<solutie[i].size();++j)
            t<<1+solutie[i][j]<<" ";
    t<<'\n';
    }
    return 0;
}