Pagini recente » Cod sursa (job #110269) | Cod sursa (job #2323123) | Cod sursa (job #3143351) | Cod sursa (job #3272327) | Cod sursa (job #381417)
Cod sursa(job #381417)
#include <cstdio>
#include <algorithm>
#include <stack>
#include <vector>
#include <set>
#define N 100005
#define mp make_pair
using namespace std;
struct nod
{
int x;
nod *n;
};
nod *a[N];
inline void add(int i, int j)
{
nod *p = new nod;
p->x = j;
p->n = a[i];
a[i] = p;
}
stack<pair<int, int> > st;
int n, m;
int dfn[N];
int low[N];
vector<vector<int> > sol;
void read()
{
freopen("biconex.in","r",stdin);
scanf("%d %d\n", &n, &m);
int x, y;
while(m--)
{
scanf("%d %d\n", &x, &y);
add(x,y);
add(y,x);
}
}
void getBiconexComponent(int fn, int n)
{
vector<int> x;
int i, j;
do
{
i = st.top().first;
j = st.top().second;
st.pop();
x.push_back(i);
x.push_back(j);
}while(fn != i && n != j);
sol.push_back(x);
}
void dfs(int n, int tn, int nr)
{
dfn[n] = low[n] = nr;
for(nod * i = a[n]; i ; i = i->n)
{
if(i->x == tn) continue;
if(dfn[i->x] == -1)
{
st.push(mp(n, i->x));
dfs(i->x, n, nr+1);
low[n] = min(low[n], low[i->x]);
if(low[i->x] >= dfn[n])
getBiconexComponent(n, i->x);
}
else low[n] = min(low[n], dfn[i->x]);
}
}
int main()
{
read();
memset(dfn, -1, sizeof(dfn));
dfs(1, 0, 0);
int i, j;
freopen("biconex.out","w",stdout);
printf("%d\n", sol.size());
for(i = 0; i < sol.size(); ++i)
{
set<int> a(sol[i].begin(), sol[i].end());
for(set<int>::iterator it = a.begin(); it != a.end(); ++it)
printf("%d ", *it);
printf("\n");
}
return 0;
}