Pagini recente » Cod sursa (job #1771492) | Cod sursa (job #1159983) | Cod sursa (job #2048130) | Cod sursa (job #488834) | Cod sursa (job #981307)
Cod sursa(job #981307)
#include <fstream>
#include <vector>
#include <bitset>
#include <queue>
#include <algorithm>
#include <utility>
#include <string.h>
#include <set>
#include <stack>
using namespace std;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
const int MAXN = 100005;
const int oo = (1<<31)-1;
typedef vector<int> Graph[MAXN];
typedef vector<int> :: iterator It;
Graph G;
int N, M, Level[MAXN], LowLink[MAXN];
stack< pair<int, int> > Stack;
vector <set <int> > Bcon;
const inline void Get_min(int &a, const int b) {
if( a>b )
a = b;
}
inline void ReadInput() {
cin >> N >> M;
for(int i = 1 ; i <= M ; ++ i){
int x, y;
cin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
}
inline void CatchBc(int X, int Y) {
int Tx, Ty;
set <int> actB;
do {
Tx = Stack.top().first;
Ty = Stack.top().second;
Stack.pop();
actB.insert(Tx);
actB.insert(Ty);
} while(Tx != X || Ty != Y);
Bcon.push_back(actB);
}
inline void DFs(int Node, int Father, int actLevel) {
Level[Node] = LowLink[Node] = actLevel;
for(It it = G[Node].begin(), fin = G[Node].end(); it != fin ; ++ it) {
if(*it == Father)
continue;
if(!Level[*it]) {
Stack.push(make_pair(Node, *it));
DFs(*it, Node, actLevel + 1);
Get_min(LowLink[Node], LowLink[*it]);
if(LowLink[*it] >= Level[Node])
CatchBc(Node, *it);
}
else Get_min(LowLink[Node], LowLink[*it]);
}
}
inline void WriteBiconex() {
cout << Bcon.size() << "\n";
for(int i = 0 ; i < Bcon.size() ; ++ i, cout << "\n")
for(set<int> :: iterator it = Bcon[i].begin(), fin = Bcon[i].end() ; it != fin ; ++ it)
cout << *it << " ";
}
int main() {
ReadInput();
DFs(1, 0, 0);
WriteBiconex();
cin.close();
cout.close();
return 0;
}