Cod sursa(job #2223584)

Utilizator Alex_AeleneiAlex Aelenei Ioan Alex_Aelenei Data 20 iulie 2018 18:14:06
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 kb
#include <cstdio>
#include <vector>
#include <utility>
using namespace std;
vector<list<int> > g, sol;
vector<int> prev, dis, low;
stack<pair<int,int> > s;
vector<bool> art;
void findart(int u, int &time,int &nr)
{
    time++;
    dis[u] = low[u] = time;
    for(int u : g[u])
    {
        if(!dis[u])
        {
            s.push(make_pair(u,u));
            prev[u] = u;
            findart(u, time, nr);
            if(low[u] >= dis[u])
            {
                int a,b;
                nr++;
                do
                {
                    a = s.top().first;
                    b = s.top().second;
                    s.pop();
                    sol[nr].push_back(b);
                }
                while(a!= u && b!= u);
                sol[nr].push_back(u);
            }
            low[u] = min(low[node],low[u]);
        }
        else
            if(u != prev[u])
                low[u] = min(low[u], low[u]);
    }
 
}
int main()
{
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    int n, m, x, y, time = 0, nr = 0;
    scanf("%d%d",&n,&m);
    g.resize(n+1);
    sol.resize(n+1);
    prev.resize(n+1, -1);
    dis.resize(n+1);
    art.resize(n+1);
    low.resize(n+1);
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d",&x,&y);
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for(int i=1; i<=n; i++)
        if(!dis[i])
            findart(i, time, nr);
    printf("%d\n",nr);
    for(int i=1; i<=nr; i++)
    {
        for(int u : sol[i])
            printf("%d ",u);
        printf("\n");
    }
    return 0;
}