Pagini recente » Cod sursa (job #1349321) | Cod sursa (job #2618445) | Cod sursa (job #1027875) | Cod sursa (job #2986538) | Cod sursa (job #2427542)
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;
vector<vector<int> > Graph(100001), Sol(100001);
stack<int> S;
pair<int, int> P[100001];
int N, M, i, j, V, VP;
bool Check[100001];
void DFS(int i);
int main()
{
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
scanf("%d%d", &N, &M);
for(i=1; i<=N; ++i) Graph[i].push_back(0);
for(i=1; i<=M; ++i){
int x, y;
scanf("%d%d", &x, &y);
Graph[x].push_back(y);
Graph[y].push_back(x);
++Graph[x][0];
++Graph[y][0];
}
for(i=1; i<=N; ++i) if(Check[i]==false) DFS(i);
printf("%d\n", V);
for(i=1; i<=V; ++i){
for(j=0; j<Sol[i].size(); ++j) printf("%d ", Sol[i][j]);
printf("\n");
}
return 0;
}
void DFS(int i){
int j;
P[i].first=P[i].second=++VP;
Check[i]=true;
S.push(i);
for(j=1; j<=Graph[i][0]; ++j){
if(Check[Graph[i][j]]==false){
DFS(Graph[i][j]);
P[i].second=min(P[i].second, P[Graph[i][j]].second);
if(P[i].first<=P[Graph[i][j]].first && P[i].first<=P[Graph[i][j]].second){
++V;
while(S.top()!=Graph[i][j]){
Sol[V].push_back(S.top());
S.pop();
}
Sol[V].push_back(S.top());
S.pop();
Sol[V].push_back(i);
}
}
else P[i].second=min(P[i].second, P[Graph[i][j]].first);
}
return;
}