Cod sursa(job #2165171)

Utilizator AlexVulpoiuAlexandru Vulpoiu AlexVulpoiu Data 13 martie 2018 11:22:23
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
int n,m,i,j,comp,t[100001],niv[100001],l[100001];
bool viz[100001];
vector <int> a[100001];
vector <vector <int> > sol;
stack <int> st;
void dfs(int k)
{
    int it,x;
    viz[k]=1;
    niv[k]=niv[t[k]]+1;
    l[k]=niv[k];
    st.push(k);
    for(it=0;it!=a[k].size();it++)
    {
        if(viz[a[k][it]])
        {
            if(a[k][it]!=t[k])
                l[k]=min(l[k],niv[a[k][it]]);
            continue;
        }
        t[a[k][it]]=k;
        dfs(a[k][it]);
        l[k]=min(l[k],l[a[k][it]]);
        if(niv[k]<=l[a[k][it]])
        {
            sol.push_back(vector<int>(0));
            do
            {
                x=st.top();
                st.pop();
                sol[comp].push_back(x);
            }
            while(x!=a[k][it]);
            sol[comp].push_back(k);
            comp++;
        }
    }
}
int main()
{
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    scanf("%d%d",&n,&m);
    while(m)
    {
        scanf("%d%d",&i,&j);
        a[i].push_back(j);
        a[j].push_back(i);
        m--;
    }
    for(i=1;i<=n;i++)
        if(!viz[i])
        {
            t[i]=0;
            dfs(i);
        }
    printf("%d\n",comp);
    for(i=0;i<sol.size();i++,printf("\n"))
        for(j=0;j<sol[i].size();j++)
            printf("%d ",sol[i][j]);
    return 0;
}