Cod sursa(job #3287184)

Utilizator PetruApostolApostol Mihnea Petru PetruApostol Data 16 martie 2025 19:50:49
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <fstream>
#include <vector>
using namespace std;

ifstream cin("biconex.in");
ofstream cout("biconex.out");

int poz,poz1;
int viz[100001],min1[100001],a1[100001];
vector<int> rasp[100001],v[100001];
void dfs(int nod,int a){
	viz[nod]=min1[nod]=a;
	poz++;a1[poz]=nod;
	for(auto it : v[nod]){///printf("%d %d\n",nod,it);
		if(!viz[it]){
			int aux=poz;
			dfs(it,a+1);
			min1[nod]=min(min1[nod],min1[it]);
			if(min1[it]>=a){
                poz1++;
				rasp[poz1].push_back(nod);
				while(aux<poz){///printf("%d\n",poz);
				    rasp[poz1].push_back(a1[poz]);poz--;
				}

			}

		}min1[nod]=min(min1[nod],viz[it]);
	}
}

int main()
{
    int n,m,i,a,b;
    cin>>n>>m;
    for(i=1;i<=m;i++){
       cin>>a>>b;
       v[a].push_back(b);
       v[b].push_back(a);
    }
    poz=0;
    dfs(1,1);
    cout<<poz1<<"\n";
    for(i=1;i<=poz1;i++){
        for(auto it: rasp[i]) cout<<it<<" ";
        cout<<"\n";
    }
    return 0;
}