Pagini recente » Cod sursa (job #1799640) | Statistici Kind Jozsef (kindjozsef) | Istoria paginii runda/utcn_grafuri_2 | Cod sursa (job #2009929) | Cod sursa (job #2901116)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
const string filename = "biconex";
ifstream fin(filename + ".in");
ofstream fout(filename + ".out");
const int maxN = 100005;
int n, m, depth[maxN], maxsus[maxN];
bool used[maxN];
vector <int> G[maxN], comp;
vector <vector <int>> bicomp;
vector <pair <int, int>> lista;
void dfs(int nod, int tata)
{
used[nod] = 1;
depth[nod] = depth[tata] + 1;
maxsus[nod] = depth[nod];
for(int vecin : G[nod])
{
if(vecin == tata)
continue;
if(used[vecin])
maxsus[nod] = min(maxsus[nod], depth[vecin]);
if(!used[vecin])
{
lista.push_back({nod, vecin});
dfs(vecin, nod);
maxsus[nod] = min(maxsus[nod], maxsus[vecin]);
if(maxsus[vecin] >= depth[nod])
{
int x, y;
do
{
x = lista.back().first;
y = lista.back().second;
lista.pop_back();
comp.push_back(x);
comp.push_back(y);
}
while(x != nod || y != vecin);
sort(comp.begin(), comp.end());
comp.erase(unique(comp.begin(), comp.end()), comp.end());
bicomp.push_back(comp);
comp.clear();
}
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
fin >> n >> m;
for(int i = 1; i <= m; i++)
{
int x, y;
fin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
dfs(1, 0);
fout << bicomp.size() << '\n';
for(auto c : bicomp)
{
for(int elem : c)
fout << elem << ' ';
fout << '\n';
}
return 0;
}