Pagini recente » Cod sursa (job #632883) | Cod sursa (job #2503783) | Cod sursa (job #2494439) | Cod sursa (job #2152011) | Cod sursa (job #3200139)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n, m;
int ord[100001], up[100001];
bool used[100001];
vector <int> stiva, curr_comp, G[100001];
vector <vector <int>> all_comps;
int cnt=0;
void dfs(int nod, int tata)
{
stiva.push_back(nod);
used[nod]=1;
up[nod]=nod;
ord[nod]=++cnt;
for(int fiu: G[nod])
{
if(fiu==tata) continue;
if(used[fiu])
{
up[nod]=min(up[nod],ord[fiu]);
continue;
}
dfs(fiu, nod);
up[nod]=min(up[nod],up[fiu]);
if(ord[nod]<=up[fiu])
{
while(stiva.back()!=fiu)
{
curr_comp.push_back(stiva.back());
stiva.pop_back();
}
curr_comp.push_back(fiu);
curr_comp.push_back(nod);
all_comps.push_back(curr_comp);
curr_comp.clear();
}
}
}
int main()
{
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);
}
for(int i = 1; i <= n; i++)
if(!used[i])
dfs(i, 0);
fout << all_comps.size() << '\n';
for(auto c : all_comps)
{
for(int x : c)
fout << x << ' ';
fout << '\n';
}
return 0;
}