Pagini recente » Cod sursa (job #2033661) | Cod sursa (job #1108234) | Cod sursa (job #2907776) | Cod sursa (job #1456019) | Cod sursa (job #1540598)
#include <cstdio>
#include <algorithm>
#include <bitset>
#include <stack>
#include <vector>
using namespace std;
const int DIM = 131072;
int nrNodes, nrEdges, nrComponents, node1, node2, Lower[DIM], Level[DIM];
stack <int> Stack; vector <int> Components[DIM], Edges[DIM]; bitset <DIM> Marked;
void DFS (int node, int level, int father) {
Marked[node] = 1;
Level[node] = level;
Lower[node] = level;
Stack.push(node);
vector <int> :: iterator it;
for (it = Edges[node].begin(); it != Edges[node].end(); it ++) {
int nextNode = *it;
if (nextNode == father)
continue;
if (!Marked[nextNode]) {
DFS (nextNode, level + 1, node);
Lower[node] = min (Lower[node], Lower[nextNode]);
if (Level[node] <= Lower[nextNode]) {
nrComponents ++;
int topNode;
do {
topNode = Stack.top();
Components[nrComponents].push_back(topNode);
Stack.pop();
} while (topNode != nextNode);
Components[nrComponents].push_back(node);
}
} else
Lower[node] = min (Lower[node], Level[nextNode]);
}
return;
}
int main () {
freopen ("biconex.in" ,"r", stdin );
freopen ("biconex.out","w", stdout);
scanf ("%d %d", &nrNodes, &nrEdges);
for (int i = 1; i <= nrEdges; i ++) {
scanf ("%d %d", &node1, &node2);
Edges[node1].push_back(node2);
Edges[node2].push_back(node1);
}
for (int i = 1; i <= nrNodes; i ++)
if (!Marked[i]) DFS (i, 1, 0);
printf ("%d\n", nrComponents);
for (int i = 1; i <= nrComponents; i ++) {
vector <int> :: iterator it;
for (it = Components[i].begin(); it != Components[i].end(); it ++) {
int node = *it;
printf ("%d ", node);
}
printf ("\n");
}
return 0;
}