Pagini recente » Cod sursa (job #2524682) | Cod sursa (job #1460309) | Cod sursa (job #38882) | Cod sursa (job #168869) | Cod sursa (job #2852782)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int NMAX = 100000;
int N, M, cnt, timp;
int tin[NMAX + 5];
int low[NMAX + 5];
bool vizitat[NMAX + 5];
vector<int> compBiconexe[NMAX + 5];
vector<int> g[NMAX + 5];
stack<int> stk;
void dfs(int fiu, int tata)
{
int copii_radacina = 0;
vizitat[fiu] = true;
low[fiu] = tin[fiu] = ++timp;
stk.push(fiu);
for(auto it : g[fiu])
{
if(it == tata)
{
continue;
}
if(vizitat[it] == true)
{
low[fiu] = min(low[fiu], tin[it]);
}
else
{
dfs(it, fiu);
low[fiu] = min(low[fiu], low[it]);
if(low[it] >= tin[fiu])
{
cnt++;
while(stk.top() != it)
{
compBiconexe[cnt].push_back(stk.top());
stk.pop();
}
compBiconexe[cnt].push_back(stk.top());
stk.pop();
compBiconexe[cnt].push_back(fiu);
}
}
}
}
int main()
{
fin >> N >> M;
while(M--)
{
int u, v;
fin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1, 0);
fout << cnt << '\n';
for(int i = 1; i <= cnt; i ++)
{
for(auto it : compBiconexe[i])
{
fout << it << ' ';
}
fout << '\n';
}
return 0;
}