Pagini recente » Cod sursa (job #774743) | Cod sursa (job #1865817) | Cod sursa (job #3036409) | Cod sursa (job #1570200) | Cod sursa (job #973265)
Cod sursa(job #973265)
#include <fstream>
#include <vector>
#include <bitset>
#include <queue>
#include <algorithm>
#include <utility>
#include <string.h>
#include <set>
#include <stack>
#define add push_back
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;
vector<int> LowLink(MAXN); ///Cel mai mic nivel care poate fi atins de descendentii sai printr-o singura muchi de intoarcere
vector<int> DfLevel(MAXN); ///Nivelul in parcurgerea Df;
vector< set<int> >BiconnectedComponent;
stack< pair<int,int> > Stack;
inline void Get_Min(int &a, int b){
if(a>b)
a=b;
}
void ExtractComponents(int X, int Y){
set<int> Comp;
int Tx, Ty;
do{
Tx = Stack.top().first;
Ty = Stack.top().second;
Stack.pop();
Comp.insert(Tx);
Comp.insert(Ty);
}while( Tx != X || Ty != Y);
BiconnectedComponent.push_back(Comp);
}
void ReadData(){
cin >> N >> M;
for(int i = 1 ; i <= M ; ++ i){
int X, Y;
cin >> X >> Y;
G[X].add(Y);
G[Y].add(X);
}
}
void DFs(int Node, int Father, int ActLevel){
DfLevel[Node] = LowLink[Node] = ActLevel;
for(It it = G[Node].begin(), fin = G[Node].end(); it != fin ; ++ it)
if(!DfLevel[*it]){
Stack.push(make_pair(Node, *it)); /// Adaug muchia in Stiva
DFs(*it, Node, ActLevel + 1);
Get_Min(LowLink[Node], LowLink[*it]);
if(LowLink[*it] >= DfLevel[Node])
ExtractComponents(Node, *it);
}
else Get_Min(LowLink[Node], DfLevel[*it]);
}
void WriteData(){
cout << BiconnectedComponent.size() << "\n";
for(vector<set<int> > :: iterator it = BiconnectedComponent.begin() , fin = BiconnectedComponent.end() ; it != fin ; ++ it, cout << "\n")
for(set<int> :: iterator i = it->begin() , j = it->end() ; i != j ; ++ i)
cout << *i << " ";
}
int main(){
ReadData();
DFs(1, 0, 1);
WriteData();
cin.close();
cout.close();
return 0;
}