Pagini recente » Cod sursa (job #2036948) | Cod sursa (job #161042) | Cod sursa (job #1040200) | Cod sursa (job #73930) | Cod sursa (job #1714478)
/** Biconnected components, implementation time 15 minutes*/
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
#include <bitset>
#define Nmax 100005
using namespace std;
typedef pair<int,int> edge;
int N,M,nrb;
vector<int> G[Nmax],Bix[Nmax];
stack<edge> S;
bitset<Nmax> used,articulation;
int level[Nmax],upperMost[Nmax];
void Read()
{
int a,b;
scanf("%d%d",&N,&M);
for(int i = 1; i <= M; ++i)
{
scanf("%d%d",&a,&b);
G[a].push_back(b);
G[b].push_back(a);
}
}
void output(int k)
{
++nrb;
///printf("Found biconnected component:\n");
edge e;
while(1)
{
e = S.top();
S.pop();
Bix[nrb].push_back(e.second);
///printf("%d %d\n",e.first,e.second);
if(e.first == k)
break;
}
Bix[nrb].push_back(k);
}
void DFS(int k,int dad)
{
used[k] = true;
level[k] = level[dad] + 1;
upperMost[k] = level[k];
for(auto it : G[k])
if(!used[it])
{
S.push({k,it});
DFS(it,k);
upperMost[k] = min(upperMost[k],upperMost[it]);
if(upperMost[it] >= level[k]) /// we can't reach any higher than k from it subtree
{
articulation[k] = true;
output(k);
}
}
else
if(it != dad && level[it] < upperMost[k]) /// back edge which reaches higher than the current root.
upperMost[k] = level[it];
}
void Output()
{
printf("%d\n",nrb);
for(int i = 1; i <= nrb; ++i)
{
for(auto it : Bix[i])
printf("%d ",it);
printf("\n");
}
}
int main()
{
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
Read();
for(int i = 1; i <= N; ++i)
if(!used[i])
DFS(i,0);
Output();
return 0;
}