Pagini recente » Cod sursa (job #1701810) | Cod sursa (job #2616098) | Cod sursa (job #649793) | Cod sursa (job #1701818) | Cod sursa (job #1020688)
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <stack>
using namespace std;
typedef struct nnode{
int low;
int distance;
} NODE;
typedef struct edge{
int a;
int b;
} EDGE;
vector<int> adjacencyList[100002];
int n,m;
NODE nodes[100002];
stack<EDGE> edgeStack;
int solutionNr;
vector<int> solution[100002];
int currentDistance = 1;
int minn(int a, int b){
if (a<b){
return a;
} else return b;
}
void dfs(int node, int from){
nodes[node].distance = currentDistance;
nodes[node].low = currentDistance;
currentDistance++;
int ss = adjacencyList[node].size();
for (int i=0; i<ss; i++){
if (!nodes[adjacencyList[node][i]].distance){
EDGE e;
e.a = node;
e.b = adjacencyList[node][i];
edgeStack.push(e);
dfs(adjacencyList[node][i], node);
if (nodes[adjacencyList[node][i]].low >= nodes[node].distance){
while (edgeStack.top().a != node){
solution[solutionNr].push_back(edgeStack.top().b);
edgeStack.pop();
}
solution[solutionNr].push_back(edgeStack.top().a);
solution[solutionNr].push_back(edgeStack.top().b);
edgeStack.pop();
solutionNr++;
}
nodes[node].low = minn(nodes[adjacencyList[node][i]].low, nodes[node].low);
} else if (adjacencyList[node][i] != from) {
nodes[node].low = minn(nodes[adjacencyList[node][i]].low, nodes[node].low);
}
}
}
int main()
{
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
scanf("%d %d", &n, &m);
int nod1, nod2;
for (int i=0; i<m; i++){
scanf("%d %d", &nod1, &nod2);
adjacencyList[nod1].push_back(nod2);
adjacencyList[nod2].push_back(nod1);
}
for (int i=1; i<=n; i++){
if (!nodes[i].distance){
dfs(i, -1);
}
}
printf("%d\n", solutionNr);
for (int i=0; i<solutionNr; i++){
for (int j=0; j<solution[i].size(); j++){
printf("%d ", solution[i][j]);
}
printf("\n");
}
return 0;
}