Pagini recente » Cod sursa (job #881159) | Cod sursa (job #2665338) | Cod sursa (job #2649172) | Cod sursa (job #2555613) | Cod sursa (job #1904383)
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
#include <set>
using namespace std;
ifstream fi("biconex.in");
ofstream fo("biconex.out");
const int Dim = 100002;
int N, M ,sp ,sol;
vector<vector<int>> G;
stack<pair<int,int>> st;
vector <int> T,index,L;
set<int> comp[Dim];
void Read_Graph()
{
int x,y;
fi>>N>>M;
G.resize(N+1);
L.resize(N+1);
index.resize(N+1);
T.resize(N+1);
for (int i = 1;i <= M; ++i)
{
fi>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
}
void Write()
{
fo<<sol<<'\n';
for (int i = 1; i <= sol; ++i,fo<<'\n')
for (auto y : comp[i])
fo<<y<<" ";
}
void Comp_biconexe(int x)
{
L[x] = index[x];
for (const int& y : G[x])
{
if ( y == T[x]) continue;
if (index[y]==0)
{ T[y] = x;
index[y] = index[x] + 1;
st.push({x, y});
Comp_biconexe(y);
L[x] = min(L[x], L[y]);
if (L[y] >= index[x])
{
++sol;
pair<int,int> p;
do {
p = st.top();
st.pop();
comp[sol].insert(p.first);
comp[sol].insert(p.second);
}
while (! ( p.first == x && p.second == y));
}
}
else L[x] = min(L[x], index[y]);
}
}
int main()
{
Read_Graph();
Comp_biconexe(1);
Write();
}