Pagini recente » Cod sursa (job #1138307) | Cod sursa (job #2809240) | Cod sursa (job #1903007) | Cod sursa (job #1699577) | Cod sursa (job #3346669)
#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, nrcomp, tint[nmax], tmin[nmax];
bool viz[nmax];
vector<int> adj[nmax], sol[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<<nrcomp<<"\n";
for(int i = 1; i <= nrcomp; ++i)
{
for(auto nod : sol[i])
fout<<nod<<" ";
fout<<"\n";
}
return 0;
}
void dfs(int nod, int tata)
{
tint[nod] = tint[tata] + 1;
tmin[nod] = tint[nod];
viz[nod] = 1;
s.push(nod);
for(auto i : adj[nod])
{
if(i == tata)
continue;
if(viz[i])
tmin[nod] = min(tmin[nod], tint[i]);
else
{
dfs(i, nod);
tmin[nod] = min({tmin[nod], tmin[i]});
if(tint[nod] <= tmin[i])
{
++nrcomp;
while(s.top() != i)
{
sol[nrcomp].push_back(s.top());
s.pop();
}
sol[nrcomp].push_back(i);
s.pop();
sol[nrcomp].push_back(nod);
}
}
}
}