Pagini recente » Cod sursa (job #51340) | Cod sursa (job #1332406) | Cod sursa (job #451277) | Cod sursa (job #1558957) | Cod sursa (job #2686541)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n, m, i, j, a[100005], min1[100005];
bool viz[100005];
vector <int> v[100005], t(100005, -1);
vector <vector <int> > sol;
stack<int> st;
void dfs(int nod)
{
int i, x;
vector<int> c;
viz[nod] = true;
a[nod] = a[t[nod]] + 1;
min1[nod] = a[nod];
st.push(nod);
for(i = 0; i < v[nod].size(); i++)
if(viz[v[nod][i]])
{
if(v[nod][i] != t[nod])min1[nod] = min(min1[nod], a[v[nod][i]]);
}
else
{
t[v[nod][i]] = nod;
dfs(v[nod][i]);
min1[nod] = min(min1[nod], min1[v[nod][i]]);
if(a[nod] <= min1[v[nod][i]])
{
c.clear();
while(!st.empty())
{
x = st.top();
st.pop();
c.push_back(x);
if(x == v[nod][i])
{
c.push_back(nod);
sol.push_back(c);
break;
}
}
}
}
}
int main()
{
fin>>n>>m;
while(m)
{
fin>>i>>j;
v[i].push_back(j);
v[j].push_back(i);
m--;
}
for(i = 1; i <= n; i++)
if(!a[i])
{
t[i] = 0;
dfs(i);
}
fout<<sol.size()<<'\n';
for(i=0;i<sol.size();i++)
{
for(j=0;j<sol[i].size();j++)fout<<sol[i][j]<<" ";
fout<<'\n';
}
return 0;
}