Pagini recente » Cod sursa (job #2927462) | Cod sursa (job #320340) | Cod sursa (job #1940401) | Cod sursa (job #159174) | Cod sursa (job #1647813)
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std ;
const int NMAX = 100005 ;
ifstream fin("biconex.in") ;
ofstream fout("biconex.out");
int N, M, sol;
vector <int> V[NMAX], SOL[NMAX] ;
int lvl[NMAX] ;
int low[NMAX], st[NMAX], top;
void Biconex(int start, int finnish)
{
sol ++ ;
while(st[top] != finnish)
{
SOL[sol].push_back(st[top]) ;
top -- ;
}
top -- ;
SOL[sol].push_back(finnish) ;
SOL[sol].push_back(start) ;
}
void DFS(int node)
{
low[node] = lvl[node] ;
top ++ ;
st[top] = node ;
for(int i = V[node].size() - 1 ; i >= 0 ; i --)
{
if(lvl[V[node][i]] == 0)
{
lvl[V[node][i]] = lvl[node] + 1 ;
DFS(V[node][i]) ;
if(low[V[node][i]] >= lvl[node])
Biconex(node, V[node][i]) ;
}
}
for(int i = V[node].size() - 1 ; i >= 0 ; i --)
if(low[V[node][i]] < low[node])
low[node] = low[V[node][i]] ;
}
int main()
{
fin >> N >> M ;
for(int i = 1 ; i <= M ; ++ i)
{
int x, y ;
fin >> x >> y ;
V[x].push_back(y) ;
V[y].push_back(x) ;
}
lvl[1] = 1 ;
top = 0 ;
DFS(1) ;
fout << sol << '\n';
for(int i = 1 ; i <= sol ; ++ i)
{
sort(SOL[i].begin(), SOL[i].end()) ;
for(vector <int> ::iterator it = SOL[i].begin(); it != SOL[i].end() ; ++ it)
fout << *it << ' ' ;
fout << '\n' ;
}
fin.close();
fout.close() ;
return 0 ;
}