Pagini recente » Cod sursa (job #1794598) | Cod sursa (job #1534007) | Cod sursa (job #1719998) | Cod sursa (job #2721051) | Cod sursa (job #1020659)
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <stack>
using namespace std;
typedef struct nnode{
int low;
int distance;
} NODE;
vector<int> adjacencyList[100002];
int n,m;
NODE nodes[100002];
stack<int> nodeStack;
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){
nodeStack.push(node);
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){
dfs(adjacencyList[node][i], node);
if (nodes[adjacencyList[node][i]].low >= nodes[node].distance){
while (nodeStack.top() != node){
solution[solutionNr].push_back(nodeStack.top());
nodeStack.pop();
}
solution[solutionNr].push_back(node);
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);
nodeStack.pop();
}
}
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;
}