Advertisement
nicuvlad76

Untitled

Nov 26th, 2020
573
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.33 KB | None | 0 0
  1. #include <fstream>
  2. #define  N 101
  3. using namespace std;
  4. ifstream fin("componenteconexe.in");
  5. ofstream fout("componenteconexe.out");
  6. struct nod
  7. {
  8.     int info;
  9.     nod*urm;
  10. }*L[N];
  11.  
  12. int viz[N];
  13.  
  14. int n,m,nd;
  15. void Citire()
  16. {
  17.     fin>>n;
  18.     int x,y;
  19.     nod*p;
  20.     while(fin>>x>>y)
  21.     {
  22.         p=new nod;
  23.         p->info=y;
  24.         p->urm=L[x];
  25.         L[x]=p;
  26.         p=new nod;
  27.         p->info=x;
  28.         p->urm=L[y];
  29.         L[y]=p; ///neorien
  30.     }
  31. }
  32. void Sortare(int nd)
  33. {
  34.     int aux;
  35.     for(nod*p=L[nd]; p->urm; p=p->urm)
  36.         for(nod*q=p->urm; q; q=q->urm)
  37.             if(p->info>q->info)
  38.             {
  39.                 aux=p->info;
  40.                 p->info=q->info;
  41.                 q->info=aux;
  42.             }
  43. }
  44. void DFS(int nd,int cc)
  45. {
  46.     nod*p;
  47.     ///fout<<nd<<' ';
  48.     p=L[nd];
  49.     viz[nd]=cc;
  50.     while(p)
  51.     {
  52.         if(viz[p->info]==0)
  53.             DFS(p->info,cc);
  54.         p=p->urm;
  55.     }
  56. }
  57.  
  58. int main()
  59. {
  60.     Citire();
  61.     for(int i=1; i<=n; i++)
  62.         Sortare(i);
  63.  
  64.     int cc=0;
  65.     for(int i=1; i<=n; i++)
  66.         if(viz[i]==0)
  67.         {
  68.             cc++;
  69.             DFS(i,cc);
  70.         }
  71.     fout<<cc<<'\n';
  72.  
  73.     for(int j=1;j<=cc;j++)
  74.     {
  75.         for(int i=1;i<=n;i++)
  76.             if(viz[i]==j)fout<<i<<' ';
  77.         fout<<'\n';
  78.     }
  79.     return 0;
  80. }
  81.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement