Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <fstream>
- #include <vector>
- #include <algorithm>
- #define N 105
- using namespace std;
- ifstream fin("autostrada.in");
- ofstream fout("autostrada.out");
- struct lista
- {
- int nod, c;
- lista *urm;
- }*g[N];
- struct Punct
- {
- int x,y;
- friend bool operator <(Punct p1, Punct p2)
- {
- if(p1.x!=p2.x)return p1.x<p2.x;
- else return p1.y<p2.y;
- }
- };
- vector <Punct> v;
- void add(int x, int y)
- {
- lista*p=new lista;
- p->nod=y;
- p->c=0;
- p->urm=g[x];
- g[x]=p;
- }
- int n,m;
- void citire()
- {
- int x,y,k;
- fin>>n>>m;
- for(k=1;k<=m;++k)
- {
- fin>>x>>y;
- add(x,y);
- add(y,x);
- }
- }
- int t[N], viz[N], niv[N], l[N];
- void DFS(int nod)
- {
- lista *p;
- int x;
- viz[nod]=1;
- l[nod]=niv[nod];
- for(p=g[nod];p; p=p->urm)
- {
- x=p->nod;
- if(!viz[x])
- {
- niv[x]=niv[nod]+1;
- t[x]=nod;
- DFS(x);
- if(l[nod]>l[x])l[nod]=l[x];
- if(l[x]>niv[nod])p->c=1;
- }
- else
- if(x!=t[nod] && l[nod]>niv[x])
- l[nod]=niv[x];
- }
- }
- int main()
- {
- lista *p;
- citire();
- Punct q;
- for(int i=1;i<=n;i++)
- if(!viz[i])
- {
- niv[i]=1;
- DFS(i);
- }
- int k=0;
- for(int i=1;i<=n;i++)
- for(p=g[i]; p; p=p->urm)
- if(p->c==1) k++;
- fout<<k<<"\n";
- for(int i=1;i<=n;i++)
- for(p=g[i];p;p=p->urm)
- if(p->c==1)
- {
- if(i>p->nod)swap(i,p->nod);
- q.x=i;
- q.y=p->nod;
- v.push_back(q);
- }
- sort(v.begin(), v.end(),less<Punct>());
- for(int i=0;i<k;i++)
- fout<<v[i].x<<" "<<v[i].y<<"\n";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment