Pagini recente » Cod sursa (job #1114511) | Cod sursa (job #2882139) | Cod sursa (job #3125150) | Cod sursa (job #1754916) | Cod sursa (job #2515096)
#include <bits/stdc++.h>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
//-----------------------------------------------------------------
///Globale
int n,nivel[100001],rasp,nr;
vector<int>muchii[100001],raspuns[200001];
bitset<100001>ap;
pair<int,int>st[200001];
//-----------------------------------------------------------------
///Functii
void citire();
void rezolvare();
void afisare();
//-----------------------------------------------------------------
int main()
{
citire();
rezolvare();
afisare();
return 0;
}
//-----------------------------------------------------------------
void afisare()
{
g << rasp << '\n';
for(int i = 1; i <= rasp; ++i)
{
for(auto nod : raspuns[i])
g << nod << " ";
g << '\n';
}
}
//-----------------------------------------------------------------
void dfs(int nod)
{
bool ver = 0;
int mi = n + 1;
int par;
for(auto vecin : muchii[nod])
if(ap[vecin] == 0)
{
ver = 1;
ap[vecin] = 1;
nivel[vecin] = nivel[nod] + 1;
st[++nr] = {nod,vecin};
dfs(vecin);
}
else if(nivel[vecin] < mi)
{
mi = nivel[vecin];
par = vecin;
}
if(nr && st[nr].second == nod)
{
rasp++;
raspuns[rasp].push_back(nod);
raspuns[rasp].push_back(par);
while(nr > 0 && st[nr].first != par)
{
raspuns[rasp].push_back(st[nr].first);
nr--;
}
if(nr)
nr--;
}
}
//-----------------------------------------------------------------
void rezolvare()
{
for(int i = 1; i <= n; ++i)
if(ap[i] == 0)
if(muchii[i].size() == 0)
continue;
else
{
ap[i] = 1;
nivel[i] = 1;
nr = 0;
dfs(i);
}
}
//-----------------------------------------------------------------
void citire()
{
int m;
f >> n >> m;
while(m--)
{
int a,b;
f >> a >> b;
muchii[a].push_back(b);
muchii[b].push_back(a);
}
f.close();
}