Pagini recente » Istoria paginii utilizator/uaic-ciocan-sarbu-puiu | Cod sursa (job #2005816) | Profil NicuBoca16 | Cod sursa (job #2004067) | Cod sursa (job #1100074)
#include <fstream>
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
#define NMAX 100010
const int oo = 200010;
int N,M,Low[NMAX],Level[NMAX],Used[NMAX],Crt,LastCriticalPoint;
vector<int> G[NMAX];
stack<int>Solution;
vector<int>SolutionsVector[NMAX];
void Read(){
f>>N>>M;
int x,y;
for (int i = 1; i <= M; i++) {
f>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
}
void RemoveFromCache(int Node ,int Neighbour)
{
while(!Solution.empty() && Solution.top() != Neighbour)
{
SolutionsVector[Crt].push_back(Solution.top());
Solution.pop();
}
if (Neighbour) {
SolutionsVector[Crt].push_back(Neighbour);
}
SolutionsVector[Crt++].push_back(Node);
if( !Solution.empty() )
Solution.pop();
}
void DFS(int Node,int Father){
Used[Node] = 1;
Level[Node] = Level[Father] + 1;
Low[Node] = Level[Node];
int Nr = 0;
for (vector<int>::iterator it = G[Node].begin(); it != G[Node].end(); ++it) {
if (Used[*it]==0) {
Nr++;
Solution.push(*it);
DFS(*it,Node);
Low[Node] = min(Low[Node],Low[*it]);
if (Low[*it] >= Level[Node]) {
if (Used[Node] != 2) {
Used[Node] = 2;
RemoveFromCache(Node, *it);
LastCriticalPoint = Node;
}
}
}else{
Low[Node] = min(Low[Node],Level[*it]);
}
}
if (Father == 0 && Nr > 1) {
Used[Node] = 2;
RemoveFromCache(Node, 0);
}
}
void Solve(){
for (int i = 1; i <= N; i++) {
if (Used[i]==0) {
DFS(i,0);
}
}
}
void Write(){
g<<Crt<<"\n";
for (int i = 0; i < Crt; i++) {
for (vector<int>::iterator it = SolutionsVector[i].begin(); it != SolutionsVector[i].end() ; it++) {
g<<*it<<" ";
}g<<"\n";
}
}
int main()
{
Read();
Solve();
Write();
return 0;
}