fork download 
  1. #include <fstream>
  2. #define nmax 1501
  3. using namespace std;
  4.  
  5. struct nod_lista{
  6.     int vecin;
  7.     nod_lista *link;
  8. };
  9.  
  10. nod_lista *G[nmax],*Last[nmax];
  11. int Viz[nmax],T[nmax],CC[nmax][nmax],Lev[nmax];
  12. int N,M,nr_cicluri;
  13.  
  14. void adauga(int unde,int ce)
  15. {
  16.     nod_lista *q=new nod_lista;
  17.  
  18.     q->vecin=ce;
  19.     q->link=NULL;
  20.     if(!G[unde])
  21.     G[unde]=Last[unde]=q;
  22.     else
  23.     {
  24.         Last[unde]->link=q;
  25.         Last[unde]=q;
  26.     }
  27. }
  28.  
  29. void citeste()
  30. {
  31.     ifstream f("police.in");
  32.     int i,x,y;
  33.  
  34.     f>>N>>M;
  35.     for(i=1;i<=M;i++)
  36.     {
  37.         f>>x>>y;
  38.         adauga(x,y);
  39.         adauga(y,x);
  40.     }
  41.  
  42.     f.close();
  43. }
  44.  
  45. void ciclu_nou(int nod,int rad)
  46. {
  47.     ++nr_cicluri;
  48.     while(nod!=rad)
  49.     {
  50.         ++CC[nr_cicluri][0];
  51.         CC[nr_cicluri][CC[nr_cicluri][0]]=nod;
  52.         nod=T[nod];
  53.     }
  54.     ++CC[nr_cicluri][0];
  55.     CC[nr_cicluri][CC[nr_cicluri][0]]=nod;
  56. }
  57.  
  58. void DFS(int nod)
  59. {
  60.     nod_lista *q=G[nod];
  61.     while(q)
  62.     {
  63.         if(!Viz[q->vecin])
  64.         {
  65.             T[q->vecin]=nod;
  66.             Viz[q->vecin]=1;
  67.             Lev[q->vecin]=Lev[nod]+1;
  68.             DFS(q->vecin);
  69.         }
  70.         else
  71.         if((q->vecin!=T[nod])&&(Lev[nod]>Lev[q->vecin]))
  72.         ciclu_nou(nod,q->vecin);
  73.  
  74.         q=q->link;
  75.     }
  76. }
  77.  
  78. void rezolva()
  79. {
  80.     int i;
  81.     for(i=1;i<=N;i++)
  82.     if(!Viz[i])
  83.     {
  84.         Viz[i]=1;
  85.         Lev[i]=1;
  86.         DFS(i);
  87.     }
  88. }
  89.  
  90. void scrie()
  91. {
  92.     ofstream g("police.out");
  93.     int i,j;
  94.  
  95.     g<<nr_cicluri<<'\n';
  96.  
  97.     for(i=1;i<=nr_cicluri;i++)
  98.     {
  99.         g<<CC[i][CC[i][0]]<<' ';
  100.         for(j=1;j<=CC[i][0];j++)
  101.         g<<CC[i][j]<<' ';
  102.  
  103.         g<<'\n';
  104.     }
  105.  
  106.     g.close();
  107. }
  108.  
  109.  
  110. int main()
  111. {
  112.     citeste();
  113.     rezolva();
  114.     scrie();
  115.     return 0;
  116. }
  117.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/oWAIye
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!