Pagini recente » Cod sursa (job #1680198) | Cod sursa (job #1336357) | Cod sursa (job #2841028) | Cod sursa (job #1647943) | Cod sursa (job #1904580)
#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,sol,root;
bool p[MAX]; // p[i] == true daca i e pct. articulatie
int t[MAX]; // sir de tati
int index[MAX]; // indexelul 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
int nr; // Nr de muchii "de arbore" (care "ies" din radacina)
bool viz[MAX];
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, int niv)
{
if ( niv == 2 ) nr++;
L[x] = index[x] = niv;
viz[x] = true;
for (const int& y : G[x])
{
if ( y == t[x] ) continue;
if ( !viz[y] ) // muchie de arbore
{
t[y] = x;
st.push({x,y});
DF(y, niv + 1);
L[x] = min(L[x], L[y]);
if(L[y]>=index[x]) Extract(x,y);
}
else L[x] = min(L[x], index[y]); // muchie de intoarcere
}
}
void PuncteArticulatie()
{
if ( nr > 1 ) p[root] = true; // rad e punct de articulatie daca din ea pleaca cel putin doua muchii de arbore
for (int i = 1; i <= n; i++ )
{
if ( i == root || t[i] == root) continue;
if ( L[i] >= index[t[i]] ) p[t[i]] = true;
}
for (int i = 1; i <= n; i++ )
if ( p[i]) fo<<i<<" ";
}
void Write()
{
fo<<sol<<'\n';
for (int i = 1; i <= sol; ++i,fo<<'\n')
for (auto y : comp[i])
fo<<y<<" ";
}
int main()
{
Read();
root = 1;
DF(root, 1);
Write();
//PuncteArticulatie();
return 0;
}