Cod sursa(job #1418410)

Utilizator tudi98Cozma Tudor tudi98 Data 12 aprilie 2015 23:49:21
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
#define Ndim 100005

int N,M;
vector<int> v[Ndim];
int low[Ndim];
int lvl[Ndim];
int ST[Ndim];
bool seen[Ndim];
vector< vector<int> > Sol;

int dfs(int s,int father)
{
    ST[++ST[0]] = s;
    low[s] = lvl[s];
    seen[s] = true;

    for(auto p: v[s]){
        if(p == father) continue;
        if(!seen[p]){
            lvl[p] = lvl[s] + 1;
            dfs(p,s);

            low[s] = min(low[s],low[p]);

            if(low[p] >= lvl[s]){
                Sol.push_back(vector<int>());

                int u = ST[ST[0]--];
                Sol.back().push_back(u);

                while(u != p){
                    u = ST[ST[0]--];
                    Sol.back().push_back(u);
                }
                Sol.back().push_back(s);
            }
        }
        else if(lvl[p] < lvl[s])            // back edge
            low[s] = min(low[s],lvl[p]);
    }
}

int main()
{
    ifstream fin("biconex.in");
    ofstream fout("biconex.out");

    fin >> N >> M;

    for(int i = 1; i <= M; i++){
        int x,y;
        fin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }

    for(int i = 1; i <= N; i++)
        if(!seen[i])
            dfs(i,0);

    fout << Sol.size() << "\n";
    for(auto p: Sol){
        for(auto j: p)
            fout << j << " ";
        fout << "\n";
    }

}