Cod sursa(job #3208559)

Utilizator AndreidreiGresoiu Liviu-Andrei Andreidrei Data 28 februarie 2024 19:47:43
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <bits/stdc++.h>
#include <cstring>
#include <cstdio>
#pragma GCC optimize ("O3")
#define din cin
#define dout out
#define pi 3.14159265359
#define sw(x,y) x^=y,y^=x,x^=y
#define bmin(a,b)((a<b)?(a):(b))
#define bmax(a,b)((a>b)?(a):(b))
#define bminify(a,b)a=bmin(a,b)
#define bmaxify(a,b)a=bmax(a,b)
#define forq(i,ii,n)for(i=ii;i<n;i++)
#define f first
#define s second
#define mod 1000000007ll
#define nmax 100002
#define lim 1001
using namespace std;
typedef long long ll;
ifstream in("biconex.in");
ofstream out("biconex.out");
//FILE *fin=fopen("infasuratoare.in","r");
//FILE *fout=fopen("infasuratoare.out","w");
int n,m,i,j,k,l,p[nmax],t[nmax],f[nmax],z,b,c[nmax];
vector<int>g[nmax],h[nmax];
void tr(int v){
p[v]=t[v]=++z,c[l++]=v;
for(auto i:g[v])
    if(i!=f[v]){
        if(p[i]==0){
            f[i]=v,tr(i);
            if(t[i]>=p[v]){
                do{
                    h[b].emplace_back(c[--l]);
                }while(c[l]!=i);
                h[b++].emplace_back(v);
            }
                else bminify(t[v],t[i]);
        }
            else bminify(t[v],p[i]);
    }
}
int main()
{
in>>n>>m;
forq(k,0,m)in>>i>>j,g[i].emplace_back(j),g[j].emplace_back(i);
f[1]=1;
tr(1);
out<<b;
forq(i,0,b){
    out<<'\n';
    for(auto j:h[i])out<<j<<' ';
}
}