Pagini recente » Cod sursa (job #256731) | Cod sursa (job #1614906) | Cod sursa (job #2593977) | Cod sursa (job #2600932) | Cod sursa (job #843790)
Cod sursa(job #843790)
#include<fstream>
#include<vector>
#include<stack>
#define MMAX 200002
#define NMAX 100002
using namespace std;
stack <int> s;
vector <int> v[NMAX],comp[NMAX];
int n,m,viz[NMAX],vm[NMAX];
int lowl[NMAX],level[NMAX],t[NMAX],nr=1;
ifstream in("biconex.in");
ofstream out("biconex.out");
void scan()
{
int a,b;
in>>n>>m;
for (int i=1;i<=m;i++)
{
in>>a>>b;
v[a].push_back(b);
v[b].push_back(a);
}
}
void componenta(int nod)
{
int a;
while (s.top()!=nod)
{
a=s.top();
comp[nr].push_back(a);
s.pop();
}
comp[nr].push_back(nod);
nr++;
}
void dfs(int nod,int lvl)
{
level[nod]=lvl;
lowl[nod]=lvl;
viz[nod]=1;
for(vector<int>::iterator it=v[nod].begin(); it!=v[nod].end();++it)
{
if (!viz[*it])
{
s.push(*it);
t[*it]=nod;
dfs(*it,lvl+1);
if (lowl[*it]<lowl[nod])
lowl[nod]=lowl[*it];
if (level[nod]<=lowl[*it])
{
componenta(nod);
}
}
else if (t[nod]!=*it)
{
if (level[*it]<lowl[nod])
lowl[nod]=level[*it];
}
}
}
void print()
{
int l;
vector <int>::iterator it;
out<<nr-1<<"\n";
nr--;
for(int l=1;l<=nr;l++)
{
for (it=comp[l].end()-1;it!=comp[l].begin();it--)
out<<*it<<" ";
out<<*it<<"\n";
}
}
int main()
{
scan();
for (int i=1;i<=n;i++)
{
if (!viz[i])
{
s.push(i);
dfs(i,1);
}
}
print();
return 0;
}