Pagini recente » Cod sursa (job #1569352) | Cod sursa (job #3349982) | Diferente pentru problema/ackermann intre reviziile 13 si 5 | Cod sursa (job #3324517) | Cod sursa (job #3337180)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n, m;
vector <int> g[100005];
vector <int> viz(100005, 0), niv(100005, 0), niv_min(100005, 0);
stack <int> s;
int nr_comp;
vector<int> comp[100005];
// 1
// 2 5
// 3
// 4
void dfs(int nod)
{
viz[nod] = 1;
s.push(nod);
niv_min[nod] = niv[nod];
for(int i = 0; i < g[nod].size(); i++)
{
int vecin = g[nod][i];
if(viz[vecin] == 0)
{
niv[vecin] = niv[nod] + 1;
dfs(vecin);
niv_min[nod] = min(niv_min[vecin], niv_min[nod]);
if(niv_min[vecin] >= niv[nod])
{
//aici e muchia critica nod - vecin
//punct critic
nr_comp++;
while(s.top() != vecin)
{
comp[nr_comp].push_back(s.top());
s.pop();
}
comp[nr_comp].push_back(vecin);
s.pop();
comp[nr_comp].push_back(nod);
}
}
else
{
if(niv[vecin] < niv[nod] - 1)
niv_min[nod] = min(niv_min[nod], niv[vecin]);
}
}
}
int main()
{
int x, y;
fin >> n >> m;
for(int i = 1; i <= m; i++)
{
fin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
for(int i = 1; i <= n; i++)
{
if(viz[i] == 0)
{
niv[i] = 1;
dfs(i);
}
}
fout << nr_comp << '\n';
for(int i = 1; i <= nr_comp; i++, fout << '\n')
for(int j = 0; j < comp[i].size(); j++)
fout << comp[i][j] << ' ';
return 0;
}