Pagini recente » Statistici Tasi Balazs (balazstasi) | Cod sursa (job #1462744) | Cod sursa (job #2124277) | Cod sursa (job #370265) | Cod sursa (job #1909258)
#include <fstream>
#include <vector>
#include <stack>
#include <set>
using namespace std;
ifstream fi("biconex.in");
ofstream fo("biconex.out");
const int MAX = 100001;
set<int> comp[MAX];
vector<int> G[MAX];
stack<pair<int,int>> st;
int n,m,ind,sol;
bool p[MAX]; // p[i] == true daca i e pct. articulatie
int index[MAX]; // indexul fiecarui nod in arborele DF
int L[MAX]; // nivel minim in arbore pe care se p ajung dintr-un nod sau
// dintr-unul dintre descendentii lui
// printr-o singura muchie de intoarcere
void Read()
{
int x, y;
fi >> n >> m;
while ( fi >> x >> y )
{
G[x].push_back(y);
G[y].push_back(x);
}
}
void Extract(int x, int y)
{
sol++;
int xs, ys;
do
{ xs = st.top().first;
ys = st.top().second;
comp[sol].insert (xs);
comp[sol].insert (ys);
st.pop();
}
while (xs != x || ys != y);
}
void DF(int x)
{
L[x] = index[x] = ind++;
for (const int& y : G[x])
if ( index[y]==0) // muchie de arbore
{
st.push({x,y});
DF(y);
L[x] = min(L[x], L[y]);
if(L[y]>=index[x]) { //p[x]=true; x este punct de articulatie
//fo<<x<<" "<<y; muchia de la x la y este de articluatie
Extract(x,y);}
}
else L[x] = min(L[x], index[y]); // muchie de intoarcere
}
void Write()
{
fo<<sol<<'\n';
for (int i = 1; i <= sol; ++i,fo<<'\n')
for (auto y : comp[i])
fo<<y<<" ";
}
int main()
{
Read();
DF(1);
Write();
return 0;
}