Cod sursa(job #2131929)

Utilizator popabogdanPopa Bogdan Ioan popabogdan Data 15 februarie 2018 10:06:38
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.64 kb
#include <bits/stdc++.h>

#define Nmax 100005

using namespace std;

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

int N, M;
int lev[Nmax], low[Nmax];
vector <int> G[Nmax];
stack < pair <int, int> > S;
vector < vector <int> > C;

void DFS(int node)
{
    low[node] = lev[node];
    for(auto it : G[node])
    {
        if(!lev[it])
        {
            lev[it] = 1 + lev[node];
            S.push(make_pair(node, it));
            DFS(it);
            low[node] = min(low[node], low[it]);
            if(low[it] >= lev[node])
            {
                vector <int> P;
                int tx, ty;
                do
                {
                    tx = S.top().first;
                    ty = S.top().second;
                    S.pop();
                    P.push_back(tx);
                    P.push_back(ty);
                }while(make_pair(tx, ty) != make_pair(node, it));
                sort(P.begin(), P.end());
                P.erase(unique(P.begin(), P.end()), P.end());
                C.push_back(P);
            }
        }
        else
            if(lev[it] != lev[node] - 1)
                low[node] = min(low[node], lev[it]);

    }
}

int main()
{
    fin >> N >> M;
    while(M--)
    {
        int x, y;
        fin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for(int i = 1; i <= N; i++)
        if(!lev[i])
        {
            lev[i] = 1;
            DFS(i);
        }
    fout << C.size() << "\n";
    for(auto V : C)
    {
        for(auto it : V)
            fout << it << " ";
        fout << "\n";
    }
    return 0;
}