Cod sursa(job #2223570)

Utilizator MoldovanAndrei1Moldovan Andrei MoldovanAndrei1 Data 20 iulie 2018 17:47:54
Problema Componente biconexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.88 kb
#include <bits/stdc++.h>
using namespace std;
int t[100005],fr[100005],in[100005],l[100005];
vector<int>v[100005];
int m=0,nods,rt=0;
stack<int>st;
vector<int>sol[100005];
int cnt1=0;
int cnt2=0;
void dfs(int ind,int s)
{
    st.push(ind);
    in[ind]=++m;
    l[ind]=m;
    t[ind]=s;
    int r=v[ind].size();
    if(r==0)return;
    int i;
    for(i=0;i<r;i++)
    {
        if(v[ind][i]==s)continue;
        int val=v[ind][i];
        if(!in[val])
        {
            if(nods==ind)rt++;
            dfs(val,ind);
if(nods==ind&&r==1)continue;
            l[ind]=min(l[ind],l[val]);
            if(l[val]>=in[ind])
            {
                fr[ind]=1;
                cnt1++;
                while(!st.empty())
                {
                    if(st.top()==ind)
                    {
                        sol[cnt1].push_back(ind);
                       //st.pop();
                        break;
                    }
                    sol[cnt1].push_back(st.top());
                    st.pop();
                }
                if(ind==nods)cnt2++;
            }
        }
        else
        {
            l[ind]=min(l[ind],l[val]);
        }
    }
}
char s[100005];
int l1[100005];
int main()
{
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    int m ,n,x,y,i;
    scanf("%d%d",&m,&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(i=1;i<=m;i++)
    {
        if(in[i])continue;
        nods=i;
        rt=0;
       // while(!st.empty())st.pop();
        cnt2=0;
        dfs(i,0);
        //if(rt<2)cnt1-=cnt2;
    }
    printf("%d\n",cnt1);
    for(i=1;i<=cnt1;i++)
    {
        int r=sol[i].size(),j;
        for(j=0;j<r;j++)
            printf("%d ",sol[i][j]);
        printf("\n");
    }
    return 0;
}