Pagini recente » Cod sursa (job #2870964) | Istoria paginii utilizator/lepoartcev | Cod sursa (job #1656554) | Statistici qwerty (pnqv27) | Cod sursa (job #966091)
Cod sursa(job #966091)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#define N 100005
#define aa first
#define bb second
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n, m;
typedef pair <int, int> muchie;
vector <int> a[N], dfn(N, -1), low(N, -1);
vector < vector<int> > sol;
stack <muchie> st;
void Citire()
{
while(m--)
{
int x, y;
fin>>x>>y;
a[x].push_back(y);
a[y].push_back(x);
}
}
void Componenta_biconexa(int n, int x)
{
vector <int> bx;
int tx, ty;
do
{
tx = st.top().aa, ty = st.top().bb;
bx.push_back(tx); bx.push_back(ty);
st.pop();
}
while(tx != n || ty != x);
sol.push_back(bx);
}
void Dfs(const int n, const int t, int num)
{
dfn[n] = low[n] = num;
for(int i=0; i<a[n].size(); i++)
{
int x = a[n][i];
if(x == t) continue;
if(dfn[x] == -1)
{
st.push(muchie(n, x));
Dfs(x, n, num+1);
low[n] = min(low[n], low[x]);
if(low[x] >= dfn[n]) Componenta_biconexa(n, x);
}
else if(x != t) low[n] = min(low[n], dfn[x]);
}
}
bool cmp(const int &a, const int &b) {return a < b;}
void Write()
{
fout<<sol.size()<<'\n';
for(int i=0; i<sol.size(); i++)
{
sort(sol[i].begin(), sol[i].end(), cmp);
fout<<sol[i][0]<<' ';
for(int j=1; j<sol[i].size(); j++)
if(sol[i][j] != sol[i][j-1]) fout<<sol[i][j]<<' ';
fout<<'\n';
}
}
int main()
{
fin>>n>>m;
Citire();
Dfs(1, 0, 0);
Write();
return 0;
}