Pagini recente » Cod sursa (job #3350617) | Cod sursa (job #3309437) | Cod sursa (job #3323078) | Cod sursa (job #3312219) | Cod sursa (job #3349141)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int nmax = 1e5+5;
void dfs(int nod, int tata);
int n, m, cntbicon, tin[nmax], tmin[nmax];
bool viz[nmax];
vector<int> adj[nmax], bicon[nmax];
stack<int> s;
int main()
{
fin>>n>>m;
for(int i = 1; i <= m; ++i)
{
int x, y;
fin>>x>>y;
adj[x].push_back(y);
adj[y].push_back(x);
}
dfs(1, 0);
fout<<cntbicon<<"\n";
for(int i = 1; i <= cntbicon; ++i)
{
for(auto nod : bicon[i])
fout<<nod<<" ";
fout<<"\n";
}
return 0;
}
void dfs(int nod, int tata)
{
tin[nod] = tin[tata] + 1;
tmin[nod] = tin[nod];
viz[nod] = 1;
s.push(nod);
for(auto f : adj[nod])
{
if(f == tata)
continue;
if(viz[f])
tmin[nod] = min(tmin[nod], tin[f]);
else
{
dfs(f, nod);
tmin[nod] = min(tmin[nod], tmin[f]);
if(tin[nod] <= tmin[f])
{
++cntbicon;
while(s.top() != f)
{
bicon[cntbicon].push_back(s.top());
s.pop();
}
s.pop();
bicon[cntbicon].push_back(f);
bicon[cntbicon].push_back(nod);
}
}
}
}