Pagini recente » Cod sursa (job #3160017) | Cod sursa (job #2120999)
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
const int Max = 100005;
vector <int> V[Max];
vector <int> Sol[Max];
stack <int> S;
int n, m;
int niv[Max];
int low[Max];
int nr;
void citire()
{
in >> n >> m;
for(int i = 0; i < m; i++)
{
int x, y;
in >> x >> y;
V[x].push_back(y);
V[y].push_back(x);
}
}
void dfs(int nod)
{
low[nod] = niv[nod];
S.push(nod);
for(auto i : V[nod])
{
if(niv[i])
low[nod]=min(low[nod],niv[i]);
else
{
niv[i] = niv[nod] + 1;
dfs(i);
low[nod] = min(low[nod],low[i]);
if(low[i] >= niv[nod])
{
Sol[nr].push_back(nod);
int f;
while(1)
{
f = S.top();
Sol[nr].push_back(f);
S.pop();
if(f==i)
break;
}
nr++;
}
}
}
}
void biconex()
{
for(int i = 1; i <= n; i++)
if(niv[i] == 0)
{
niv[i] = 1;
dfs(i);
}
}
int main()
{
citire();
biconex();
for(int i = 0;i < nr; i++)
sort(Sol[i].begin(),Sol[i].end());
out << nr <<'\n';
for(int i = 0; i < nr; i++)
{
for(auto j : Sol[i])
out<<j<<' ';
out<<'\n';
}
return 0;
}