Pagini recente » Cod sursa (job #299105) | Cod sursa (job #2090205) | Cod sursa (job #1016358) | Cod sursa (job #2138191) | Cod sursa (job #1392058)
#include<fstream>
#include<vector>
#include<algorithm>
#define N 100100
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int n,m,i,x,y,j,nr,viz[N],mini[N],niv[N];
vector<int>v[N],s[N];
vector<pair<int,int> >vec;
inline void adauga(int x, int y){
s[++nr].push_back(x);
s[nr].push_back(y);
while(!vec.empty() && !(vec.back().first == x && vec.back().second == y || (vec.back().first == y && vec.back().second == x)))
{
s[nr].push_back(vec.back().first);
s[nr].push_back(vec.back().second);
vec.pop_back();
}
vec.pop_back();
}
inline void dfs(int x,int t){
viz[x] = 1;
for(vector<int>::iterator it = v[x].begin(); it != v[x].end(); ++it)
if(!viz[*it])
{
mini[*it] = niv[*it] = niv[x] + 1;
vec.push_back(make_pair(x, *it));
dfs(*it, x);
mini[x] = min(mini[x], mini[*it]);
if(mini[*it] >= niv[x])
adauga(x, *it);
}
else
if(*it != t)
mini[x] = min(niv[*it], mini[x]);
}
int main()
{
f >> n >> m;
for(i = 1; i <= m; ++i)
{
f >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1, 0);
g << nr << '\n';
for(i = 1; i <= nr; ++i)
{
sort(s[i].begin(),s[i].end());
g << s[i][0] << ' ';
for(j = 1; j < s[i].size(); ++j)
if(s[i][j] != s[i][j - 1])
g << s[i][j] << ' ';
g << '\n';
}
return 0;
}