Pagini recente » Clasament .com 2009, Runda 2 | Cod sursa (job #1187448) | Cod sursa (job #8749) | Monitorul de evaluare | Cod sursa (job #1330535)
#include <fstream>
#include <vector>
#include <stack>
#define Nmax 100100
#define neighbour Graph[node][i]
using namespace std;
vector <int> Graph[Nmax], Component[Nmax];
stack < pair<int, int> > Stack;
int N, nrC, Level[Nmax], High[Nmax];
inline void addEdge(int a, int b) {
Stack.push(make_pair(a, b));
}
void saveComponent(int a, int b) {
int x, y;
nrC++;
do {
x = Stack.top().first;
y = Stack.top().second;
Component[nrC].push_back(y);
Stack.pop();
} while(x != a && y != b);
Component[nrC].push_back(x);
}
void BellmanFord(int node, int father) {
Level[node] = Level[father] + 1;
High[node] = Level[node];
for(int i = 0; i < Graph[node].size(); i++)
if(neighbour != father) {
if(Level[neighbour] == 0) {
addEdge(node, neighbour);
BellmanFord(neighbour, node);
if(High[neighbour] >= Level[node])
saveComponent(node, neighbour);
}
if(High[neighbour] < High[node])
High[node] = High[neighbour];
}
}
void Read() {
int x, y, M;
ifstream in("biconex.in");
in >> N >> M;
while(M--) {
in >> x >> y;
Graph[x].push_back(y);
Graph[y].push_back(x);
}
in.close();
}
void Write() {
int i, j;
ofstream out("biconex.out");
out << nrC << '\n';
for(i = 1; i <= nrC; i++) {
for(j = 0; j < Component[i].size(); j++)
out << Component[i][j] << ' ';
out << '\n';
}
out.close();
}
int main() {
Read();
BellmanFord(1, 0);
Write();
return 0;
}