Cod sursa(job #3159147)

Utilizator AndreidreiGresoiu Liviu-Andrei Andreidrei Data 20 octombrie 2023 19:42:25
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 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 777777777ll
#define nmax 120001
using namespace std;
typedef long long ll;
//ifstream in("biconex.in");
//ofstream out("biconex.out");
FILE *fin=fopen("biconex.in","r");
FILE *fout=fopen("biconex.out","w");
int n,m,i,j,k,l,f[nmax],p[nmax],r[nmax],z,c[nmax*2],b;vector<int>g[nmax],h[nmax*2];
void t(int v){
    p[v]=r[v]=++z,c[l++]=v;
    for(auto i:g[v])
        if(i!=f[v])
            if(!p[i]){
                f[i]=v,t(i);
                if(r[i]>=p[v]){
                    do{
                        h[b].emplace_back(c[--l]);
                    }while(c[l]!=i);
                h[b++].emplace_back(v);
                }
                    else bminify(r[v],r[i]);
            }
                else bminify(r[v],p[i]);
}
int main()
{
fscanf(fin,"%d%d",&n,&m);
for(k=0;k<m;k++)
    fscanf(fin,"%d%d",&i,&j),g[i].emplace_back(j),g[j].emplace_back(i);
for(i=1;i<=n;i++)
    if(!p[i])
        t(i);
fprintf(fout,"%d",b);
for(i=0;i<b;i++){
    fputs("\n",fout);
    for(auto j:h[i])fprintf(fout,"%d ",j);
}
}