Pagini recente » Cod sursa (job #281779) | Cod sursa (job #678358) | Cod sursa (job #1238957) | Cod sursa (job #1487010) | Cod sursa (job #2744263)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
#define nmax 100005
stack<pair<int,int> >stk;
vector<vector<int> >comp;
bool visited[nmax];
int low[nmax];
int depth[nmax];
void add(int x, int y) {
int a,b;
vector<int> c;
do {
a = stk.top().first;
b = stk.top().second;
c.push_back(a);
c.push_back(b);
stk.pop();
} while(!stk.empty() && (a != x || b != y));
sort(c.begin(), c.end());
comp.push_back(c);
}
void art_point(vector<vector<int>>&adj,int i,int f)
{
visited[i]=true;
low[i]=depth[i]=depth[f]+1;
for(auto ni :adj[i])
{
if (!visited[ni])
{
stk.push({i,ni});
art_point(adj,ni,i);
if(low[ni]>=depth[i])
add(i,ni);
low[i]=min(low[i],low[ni]);
}
else if(ni!=f)
low[i]=min(low[i],depth[ni]);
}
}
int main()
{
ifstream be("biconex.in");
ofstream ki("biconex.out");
int n,m;
be>>n>>m;
vector<vector<int> > adj(n+1);
for(int i=0;i<m;i++)
{
int x,y;
be>>x>>y;
adj[x].push_back(y);
adj[y].push_back(x);
}
for(int i=1;i<=n;i++)
if(!visited[i])
art_point(adj,i,0);
ki<<comp.size()<<'\n';
for(auto ni : comp)
{
for(int i=0;i<ni.size();i++)
{
if(i==0 || ni[i]!=ni[i-1])
ki<<ni[i]<<" ";
}
ki<<'\n';
}
return 0;
}