Pagini recente » Cod sursa (job #1965714) | Cod sursa (job #231546) | Cod sursa (job #1932076) | Pachetul de instalare | Cod sursa (job #1552828)
#include <fstream>
#include <vector>
#include <stack>
#include <string.h>
#define NMax 100010
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int nodes, edges, prenum[NMax], low[NMax], pren, father[NMax], numComp;
bool mark[NMax], alreadyDisp[NMax];
vector<int> G[NMax], biComp[NMax];
struct edge {
int n1;
int n2;
};
stack<edge> mStack;
int getMin(int a, int b)
{
if (a < b)
return a;
return b;
}
void DFS(int node)
{
mark[node] = true;
prenum[node] = ++pren;
low[node] = pren;
for (vector<int>::iterator it = G[node].begin(); it != G[node].end(); it++) {
edge edg;
edg.n1 = node;
edg.n2 = *it;
if (!mark[*it]) {
mStack.push(edg);
father[*it] = node;
DFS(*it);
low[node] = getMin(low[node], low[*it]);
if (low[*it] >= prenum[node]) {
++numComp;
while (mStack.top().n1 != node && mStack.top().n2 != *it) {
biComp[numComp].push_back(mStack.top().n1);
biComp[numComp].push_back(mStack.top().n2);
mStack.pop();
}
biComp[numComp].push_back(node);
biComp[numComp].push_back(*it);
}
}
else if ((father[node] != *it) && (prenum[*it] < prenum[node])) {
mStack.push(edg);
low[node] = getMin(low[node], prenum[*it]);
}
}
}
int main()
{
f >> nodes >> edges;
int n1, n2;
for (int i = 1; i <= edges; i++) {
f >> n1 >> n2;
G[n1].push_back(n2);
G[n2].push_back(n1);
}
for (int i = 1; i <= nodes; i++) {
if (!mark[i])
DFS(i);
g << numComp << "\n";
for (int i = 1; i <= numComp; i++) {
memset(alreadyDisp, 0, sizeof(alreadyDisp));
for (vector<int>::iterator it = biComp[i].begin(); it != biComp[i].end(); it++) {
if (!alreadyDisp[*it]) {
g << *it << " ";
alreadyDisp[*it] = true;
}
}
g << "\n";
}
return 0;
}
}