Pagini recente » Cod sursa (job #88230) | Cod sursa (job #2042911) | Cod sursa (job #2534371) | Cod sursa (job #2564016) | Cod sursa (job #1161495)
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
ifstream in ("biconex.in");
ofstream out ("biconex.out");
const int MAXN = 100001;
const int MAXM = 200001;
typedef pair <int, int> PII;
class Stack
{
private:
PII St[MAXM];
int Size;
public:
Stack ()
{
Size = 0;
memset (St, 0, sizeof (St));
}
inline void push (const int &X, const int &Y)
{
Size ++;
St[Size] = make_pair (X, Y);
}
inline void pop ()
{
Size --;
}
inline PII top ()
{
return St[Size];
}
inline bool isEmpty ()
{
return !Size;
}
} S;
vector <int> Graf[MAXN];
vector < vector <int> > Sol;
int Low[MAXN], D[MAXN];
void Baga_Componenta (const int &X, const int &Y)
{
PII top;
vector <int> Comp;
do{
top = S.top ();
S.pop ();
Comp.push_back (top.first);
Comp.push_back (top.second);
} while (top.first != X || top.second != Y);
Sol.push_back (Comp);
}
void DFS (int nod, int father)
{
D[nod] = D[father] + 1;
Low[nod] = D[nod];
vector <int> :: iterator it;
for (it = Graf[nod].begin (); it != Graf[nod].end (); ++ it)
if (*it != father){
if (D[*it] == 0){
S.push (nod, *it);
DFS (*it, nod);
Low[nod] = min (Low[nod], Low[*it]);
if (Low[*it] >= D[nod])
Baga_Componenta (nod, *it);
}
else
Low[nod] = min (Low[nod], D[*it]);
}
}
int main()
{
int N, M, a, b, i;
in >> N >> M;
for (i = 1; i <= M; i ++){
in >> a >> b;
Graf[a].push_back (b);
Graf[b].push_back (a);
}
DFS (1, 0);
int Ans = Sol.size ();
vector <int> :: iterator it;
out << Ans << "\n";
for (size_t i = 0; i < Ans; i ++){
sort (Sol[i].begin (), Sol[i].end ());
Sol[i].erase (unique (Sol[i].begin (), Sol[i].end ()), Sol[i].end ());
for (it = Sol[i].begin (); it != Sol[i].end (); ++ it)
out << *it << " ";
out << "\n";
}
return 0;
}