Cod sursa(job #3374298)
| Utilizator | Data | 8 noiembrie 2026 22:16:55 | |
|---|---|---|---|
| Problema | Componente biconexe | Scor | 100 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 2.09 kb |
#include <bits/stdc++.h>
//#define int long long
using namespace std;
int tin[100001];
vector<int>M[100001];
int low[100001];
int timp ;
int n,m;
vector<set<int>>ans;
stack<pair<int,int>>ss;
void dfs(int nod,int tata)
{
timp++;
tin[nod] = low[nod] = timp;
for(auto i : M[nod])
{
if(i == tata)
continue;
if(tin[i]){
low[nod] = min(low[nod],tin[i]);
if(tin[i] < tin[nod])
{
ss.push({nod,i});
}
}
else{
ss.push({nod,i});
dfs(i,nod);
low[nod] = min(low[nod],low[i]);
if(low[i]>=tin[nod])
{
set<int>temp;
while(1)
{
pair<int,int>pp = ss.top();
ss.pop();
int st = pp.first,dr = pp.second;
temp.insert(st),temp.insert(dr);
if(st == nod && dr == i)
break;
}
ans.push_back(temp);
}
}
}
}
signed main() {
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
timp =0;
cin >> n >> m;
for(int i = 1;i<m+1;++i)
{
int a,b;
cin >> a >> b;
M[a].push_back(b),M[b].push_back(a);
}
for(int i = 1;i<=n;++i)
if(!tin[i ])
dfs(i,0);
cout << ans.size() << endl;
for(int i = 0;i<ans.size();++i)
{
for(auto j : ans[i])
cout << j << " ";
cout << endl;
}
return 0;
}
