Pagini recente » Cod sursa (job #1933497) | Cod sursa (job #3227622) | Cod sursa (job #2286319) | Cod sursa (job #333321) | Cod sursa (job #1028179)
#include <iostream>
#include <fstream>
#include <vector>
#define N_MAX 100001
#define M_MAX 200001
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
vector <int> v[N_MAX];
bool visited[N_MAX];
int cc = 0, N, M, st[2][M_MAX], L[N_MAX], s, ss, bc[N_MAX / 2][100], b, pst[N_MAX];
void DFS(int node)
{
/*cout<<endl<<"S:"<<s<<endl;
for(int i = 0; i < s; i++)
cout << st[0][i] << st[1][i];*/
for(int i = 0; i < v[node].size(); i++)
{
//cout<<ss<<endl;
if(visited[v[node][i]] && L[v[node][i]] < L[node] - 1)
{
int bb = 1;
//cout<<"DA";
ss = pst[v[node][i]];
while(st[1][ss] != node)
{
//cout<<"SS"<<ss;
bc[b][bb++] = st[0][ss++];
st[0][ss - 1] = 0;
st[1][ss - 1] = 0;
if(st[1][ss] == node){ bc[b][bb++] = st[0][ss]; bc[b][bb] = st[1][ss]; st[0][ss] = 0;}
}
st[1][ss] = 0;
//bc[b][bb] = st[1][ss-1];
bc[b][0] = bb;
b++;
}
if(!visited[v[node][i]])
{
L[v[node][i]] = L[node] + 1;
st[0][s] = node;
pst[node] = s;
st[1][s++] = v[node][i];
visited[v[node][i]] = true;
DFS(v[node][i]);
}
//if(i == v[node].size() - 1) ass--;
}
}
int main()
{
in >> N >> M;
for(int i = 0; i < M; i++)
{
int x, y;
in >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
visited[1] = 1;
L[1] = 1;
pst[1] = 0;
ss = s;
DFS(1);
for(int i = 0; i < s; i++)
{
while(st[0][i] == 0)
i++;
if(st[0][i] != 0)
{
int bb = 1;
bc[b][bb++] = st[0][i];
bc[b][bb] = st[1][i];
bc[b][0] = bb;
b++;
}
}
out << b <<"\n";
for(int i = 0; i < b; i++)
{
for(int j = 1; j <= bc[i][0]; j++)
out << bc[i][j] << " ";
out<<"\n";
}
return 0;
}