Cod sursa(job #2870328)

Utilizator MoldovanAndrei1Moldovan Andrei MoldovanAndrei1 Data 12 martie 2022 11:43:41
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.81 kb
#include <bits/stdc++.h>
using namespace std;
int t[100005],fr[100005],in[100005],l[100005];
vector<int>v[100005];
int m=0;
struct dd
{
    int x,y;
};
stack<dd>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])
        {
            dd v1;
            v1.x=ind;
            v1.y=val;
            st.push(v1);
            dfs(val,ind);
            l[ind]=min(l[ind],l[val]);
            if(l[val]>=in[ind])
            {
                fr[ind]=1;
                cnt1++;
                while(!st.empty())
                {
                    if(st.top().x==v1.x&&st.top().y==v1.y)
                    {
                        sol[cnt1].push_back(v1.x);
                       sol[cnt1].push_back(v1.y);
                       st.pop();
                        break;
                    }
                    sol[cnt1].push_back(st.top().y);
                    st.pop();
                }
            }
        }
        else
        {
            l[ind]=min(l[ind],in[val]);
        }
    }
    // if(fr[ind])st.pop();
}
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);
    }
    dfs(1,0);
    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;
}