Cod sursa(job #3236379)

Utilizator paull122Paul Ion paull122 Data 28 iunie 2024 12:52:53
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.59 kb
#include <bits/stdc++.h>

#define VMAX 100
#define NMAX 100000
#define LOG 21
#define INF (int)(10e8)
#define MOD 1000000007
#define ll  long long int

#define x first
#define y second

using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");

int n,m,k;
vector<int> adj[NMAX+1],compb[NMAX+1];
bool vis[NMAX+1];
int niv[NMAX+1],nma[NMAX+1];
stack<int> S;

void dfs(int x,int tx)
{
    vis[x]=1;
    niv[x]=niv[tx]+1;
    nma[x]=niv[x];
    S.push(x);

    for(int i : adj[x])
    {
        if(vis[i]&&i!=tx)
        {
            nma[x]=min(nma[x],niv[i]);
        }
        else if(!vis[i])
        {
            dfs(i,x);
            nma[x]=min(nma[x],nma[i]);
            if(niv[x]<=nma[i])
            {
                ++k;
                while(S.top()!=i)
                {
                    compb[k].push_back(S.top());
                    S.pop();
                }
                compb[k].push_back(S.top());
                S.pop();
                compb[k].push_back(x);
            }
        }
    }
}
int main()
{
    int n,m;
    fin >> n >> m;
    while(m--)
    {
        int x,y;
        fin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    dfs(1,0);
    bool conex=1;
    for(int i=1;i<=n;i++)
    {
        conex &= vis[i];
    }
    if(!conex)
    {
        fout << 0;
        return 0;
    }
    fout << k << "\n";
    for(int i=1;i<=k;i++)
    {
        for(int j : compb[i])
        {
            fout << j << " ";
        }
        fout << "\n";
    }
}