Cod sursa(job #2206257)

Utilizator roxana.aeleneiAelenei Roxana roxana.aelenei Data 21 mai 2018 22:24:35
Problema Componente biconexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include<bits/stdc++.h>
using namespace std;
vector<list<int> > G, Sol;
vector<int> Prev, Disc, Low;
stack<pair<int,int> > S;
vector<bool> ArticVertex;
void FindArticVertex(int node, int &time,int &nr)
{
    time++;
    Disc[node] = Low[node] = time;
    for(int u : G[node])
    {
        if(!Disc[u])
        {
            S.push(make_pair(node,u));
            Prev[u] = node;

            FindArticVertex(u, time, nr);
            if(Low[u] >= Disc[node])
            {
                int a,b;
                nr++;
                do{
                    a = S.top().first;
                    b = S.top().second;
                    S.pop();
                    Sol[nr].push_back(b);
                  }while(a!= node && b!= u);
                Sol[nr].push_back(node);
            }
            Low[node] = min(Low[node],Low[u]);
        }
        else
            if(u != Prev[node])
                Low[node] = min(Low[node], Low[u]);
    }

}
int main()
{
    ifstream in("biconex.in");
    ofstream out("biconex.out");
    int n, m, x, y, time = 0, nr = 0;
    in>>n>>m;
    G.resize(n+1);
    Sol.resize(n+1);
    Prev.resize(n+1, -1);
    Disc.resize(n+1);
    ArticVertex.resize(n+1);
    Low.resize(n+1);
    for(int i=1; i<=m; i++)
    {
        in>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for(int i=1; i<=n; i++)
        if(!Disc[i])
            FindArticVertex(i, time, nr);
    out<<nr<<'\n';
    for(int i=1; i<=nr; i++)
    {
        for(int u : Sol[i])
            out<<u<<" ";
        out<<'\n';
    }
    return 0;
}