Cod sursa(job #2814310)

Utilizator AndreeaCreitaCreita Andreea AndreeaCreita Data 7 decembrie 2021 22:05:27
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 5.88 kb
#include <bits/stdc++.h>
using namespace std;

#define maxi 100005

ifstream in("ctc.in");
ofstream out("ctc.out");
class Graf
{

   int n,m; //n- nr noduri, m- nr muchii
   int x,y; //muchie stg-dr

   int viz[100005]; //pt dfs
   vector<int> *l;



   public:
       Graf();
       //dfs
       void citireDFS();
       void dfs(int s);
       void nrCompCone();
       //bfs
       int citireBFS();
       void bfs(int s);
       //toposort
       void sort_top_dfs(int s, vector<int>& );
       void citire_top_dfs();
       void sortare_topologica();
       //compTareConexe
       void citire_ctc(vector<int>[],vector<int>[]);
       void dfs1(int s,vector<int>[], vector<int>&,int []);
       void dfs2(int s,vector<int>[], vector<int>[], int [],int);
       void ctc();
        //HAVEL
        void havel_hakimi();
        //PaduriMultDisj
        void citire_paduri();
        int find_radacina(int);
        void unite(int, int);
        void paduri();

};

Graf::Graf() {
    n = m = x = y = 0;
    l = new vector<int>[maxi];
    //l2 = new vector<int>[maxi];
}


void Graf::citireDFS()
{
    in>>n>>m;
    int x,y;
    for(int i =0; i<m; i++)
    {
        in>>x>>y;
        l[x].push_back(y);
        l[y].push_back(x);
    }
}
void Graf:: dfs(int s)
{
    viz[s]=1;
    for(auto el:l[s])
    {
        if(viz[el]==0)
        {
            dfs(el);
        }
    }

}

void Graf::nrCompCone()
{
    int c_con=0;
    for(int i=1; i<=n; i++)
    {
        if(viz[i]==0)
        {
            dfs(i);
            c_con++;
        }
    }
    out<<c_con;
}


int Graf :: citireBFS()
{
    int s;
    in>>n>>m>>s;

    int x,y;
    for(int i =0; i<m; i++)
    {
        in>>x>>y;
        l[x].push_back(y);
    }
    return s;
}

void Graf::bfs(int s)
{

    //int vizitat[10000];
    queue<int> q;
    int dist[100005];
    for(int i =1; i<=n; i++)
    {
        dist[i]=-1;
    }
    int v;
    q.push(s);
    viz[s] = 1;
    dist[s]=0;
    while(!q.empty())
    {

        v=q.front();
        for(auto el:l[v])
        {

            if(dist[el]==-1)
            {
                q.push(el);
                viz[el]=1;
                dist[el]=dist[v]+1;

            }

        }
        q.pop();
    }


    for(int i = 1; i<=n; i++)
    {

        out << dist[i]<<' ';
    }

}

void Graf :: citire_top_dfs()
{
    in>>n>>m;
    int x,y;
    for(int i=0;i<m;i++)
    {
        in>>x>>y;
        l[x].push_back(y);
    }
}
void Graf::sort_top_dfs(int s, vector<int> &sortop)
{

    viz[s]=1;
    for(auto el:l[s])
    {
        if(viz[el]==0)
        {
            sort_top_dfs(el, sortop);
        }

    }
    sortop.push_back(s);
}
void Graf::sortare_topologica()
{
       vector <int> sortop;
    for(int i=1; i<=n; i++)
    {
        if(viz[i]==0)
        {
            sort_top_dfs(i, sortop);
        }
    }
    reverse(sortop.begin(),sortop.end());
    for(int i:sortop)
    {
        out<<i<<" ";
    }
}

//CTC
void Graf::citire_ctc(vector<int>graf1[],vector<int>graf2[])
{


    in>>n>>m;
    int x,y;
    for(int i=0;i<m;i++)
    {
        in>>x>>y;
        graf1[x].push_back(y);
        graf2[y].push_back(x);
    }
}
void Graf::dfs1(int s,vector<int>graf1[], vector<int> &sortop, int viz1[])
{


    viz1[s]=1;
    for(auto el:graf1[s])
    {
        if(viz1[el]==0)
        {
            dfs1(el,graf1, sortop,viz1);
        }

    }
    sortop.push_back(s);
}
void Graf::dfs2(int s,vector<int>graf2[], vector<int> comp[], int viz2[],int comp_curenta)
{


    viz2[s] = 1;
    comp[comp_curenta].push_back(s);
    for(auto el:graf2[s])
    {
        if(viz2[el]==0)
        {
            dfs2(el,graf2,comp,viz2,comp_curenta);
        }
    }
}
void Graf::ctc()
{

    int *viz1 = new int [100005];
    int *viz2 = new int [100005];
    for(int i=0; i<100005; ++i)
    {
        viz1[i]=0;
    }
    for(int i=0; i<100005; ++i)
    {
        viz2[i]=0;
    }


    vector <int> *graf1 = new vector<int>[100005];
    vector <int> *graf2 = new vector<int> [100005];
    int comp_curenta=0;
     vector <int> sortop;
     vector <int> *comp = new vector<int> [100005];

    citire_ctc(graf1,graf2);

     for(int i=1; i<=n; i++)
    {

        if(viz1[i]==0)
        {

            dfs1(i,graf1,sortop,viz1);
        }
    }

    reverse(sortop.begin(),sortop.end());

    for(int i:sortop)
    {
        if(viz2[i]==0)
        {

            dfs2(i,graf2,comp,viz2,comp_curenta);
            comp_curenta++;
        }
    }
    out<<comp_curenta<<'\n';
    for(int i=0; i<comp_curenta; i++)
    {
        for(int j = 0; j < comp[i].size(); j++)
        {
            out<<comp[i][j]<<" ";

        }
        out<<'\n';
    }
}


//HAVEL HAKIMI
void Graf::havel_hakimi()
{
    vector <int> v;
    int from, to;
    in>>n;
    int i;
    for(i=0;i<n;i++)
    {
        int w;
        in>>w;
        v.push_back(w);
    }
    sort(v.begin(), v.end());
    for(from = n-1; from>=0; from--)
    {
        for(to = from -1; to >=0; to--)
        {
            if(v[to]>0 && v[from]>0)
            {
                v[from]--;
                v[to]--;

            }
        }
        if(v[from]>0)
        {
            out<<"Nu";
            break;
        }
      sort(v.begin(), v.begin()+from+1);
    }
    out<<"Da";
}
int main()
{

    /*Graf g4;
    g4.havel_hakimi();
*/

   //CTC
   Graf g5;
   g5.ctc();
   /*
    //SORTOP

    Graf g3;
    g3.citire_top_dfs();
    g3.sortare_topologica();
    */

   /*
   BFS
    int ss; //stocheaza ce returneaza citirea (nodul s initial)
    Graf g2;
    ss=g2.citireBFS();
    g2.bfs(ss);
   */


    /*
    DFS
    Graf g1;
    g1.citireDFS();

    g1.nrCompCone();
    */
    return 0;
}