Pagini recente » Cod sursa (job #437512) | Cod sursa (job #1172941) | Cod sursa (job #2582165) | Cod sursa (job #390871) | Cod sursa (job #972825)
Cod sursa(job #972825)
#include <fstream>
#include <vector>
#include <bitset>
#include <algorithm>
#include <stack>
#include <set>
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;
vector<int> Dfn(MAXN, -1), Low(MAXN);
stack< pair<int, int> > Stack;
vector< set<int> > BConx;
int n, m;
inline void Get_min(int &a, int b)
{
if(a > b)
a = b;
}
inline void ReadData(){
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 Get_Biconex(const int x, const int y){
set<int> ActBconx;
int X, Y;
do{
X = Stack.top().first;
Y = Stack.top().second;
Stack.pop();
ActBconx.insert(X);
ActBconx.insert(Y);
}while(X != x || Y != y);
BConx.push_back(ActBconx);
}
inline void DFs(int Node, int Father, int actLevel){
Dfn[Node] = Low[Node] = actLevel;
for(It it = G[Node].begin(), fin = G[Node].end() ; it != fin ; ++ it)
if(*it != Father){
if(Dfn[*it] == -1){
Stack.push(make_pair(Node, *it));
DFs(*it, Node, actLevel + 1);
Get_min(Low[Node], Low[*it]);
if(Low[*it] >= Dfn[Node])
Get_Biconex(Node, *it);
}
else Get_min(Low[Node], Dfn[*it]);
}
}
inline void WriteData(){
cout << BConx.size() << "\n";
for(vector< set<int> > :: iterator it = BConx.begin(), fin = BConx.end(); it != fin ; ++ it){
for(set<int> :: iterator i = it->begin(), j = it->end() ; i != j ; ++ i)
cout << *i << " ";
cout << "\n";
}
}
int main(){
ReadData();
DFs(1, 0, 0);
WriteData();
cin.close();
cout.close();
return 0;
}