Cod sursa(job #2283723)

Utilizator BiancaMariaVulsanVulsan Bianca Maria BiancaMariaVulsan Data 15 noiembrie 2018 20:03:20
Problema Obiective Scor 5
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.63 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <string.h>
#define nmax 32005
#define tmax 100005
using namespace std;
ifstream f("obiective.in");
ofstream g("obiective.out");
int n,m,T, st[nmax], use[nmax], nrc, nrmi, c1,c2, ok;
vector <int> v[nmax], vt[nmax], ctc[nmax], gr[nmax], grt[nmax];
vector < pair<int,int> > t;

void citire()
{
    int i,x,y;
    f>>n>>m;
    for(i=1; i<=m; i++)
    {
        f>>x>>y;
        v[x].push_back(y);
        vt[y].push_back(x);
    }
    f>>T;
    for(i=1; i<=T; i++)
    {
        f>>x>>y;
        t.push_back({x,y});
    }
}

void dfs(int nod)
{
    use[nod]=1;
    int i;
    for(i=0; i<v[nod].size(); i++)
        if(!use[v[nod][i]])
    {
        dfs(v[nod][i]);
    }
    st[++st[0]]=nod;
}

void dfst(int nod)
{
    use[nod]=0;
    int i;
    for(i=0; i<vt[nod].size(); i++)
        if(use[vt[nod][i]])
    {
        dfst(vt[nod][i]);
    }
    ctc[nrc].push_back(nod);
}

void tare_conex()
{
    int j;
    for(j=1; j<=n; j++)
        if(!use[j])
        dfs(j);
    for(j=n; j>=1; j--)
        if(use[st[j]])
    {
        nrc++;
        dfst(st[j]);
    }
}

void dfs_grafNou(int nod)
{
    int k;
    use[nod]=1;
    if(nod==c2)
        { ok=1; return;}
    for(k=0; k<gr[nod].size(); k++)
        if(!use[gr[nod][k]])
        dfs_grafNou(gr[nod][k]);
}

void dfst_grafNou(int nod)
{
    int k;
    use[nod]=1;
    if(nod==c2)
        return;
    nrmi++;
    for(k=0; k<grt[nod].size(); k++)
        if(!use[grt[nod][k]])
        dfst_grafNou(grt[nod][k]);
}

void fa_graful_componentelor()
{
    int i,j,k,l, nod1, nod2;
    //pt fiecrae componenta nodului din componenta conexa respectiva
    for(i=1; i<nrc; i++)
    for(l=0; l<ctc[i].size(); l++)
    {
        nod1=ctc[i][l];
      // verific daca are legatura cu vreun nod al altei componente conexe
      for(j=i+1; j<=nrc; j++)
      for(k=0; k<ctc[j].size(); k++)
        {
           nod2=ctc[j][k];
            //daca am muchie intre doua noduri apartinand a doua comp conexe dif
            if(find(v[nod1].begin(), v[nod1].end(), nod2)!= v[nod1].end())
                if(find(gr[j].begin(), gr[j].end(), i)==gr[j].end())
                {grt[j].push_back(i); gr[i].push_back(j);}
            if(find(v[nod2].begin(), v[nod2].end(), nod1)!= v[nod2].end())
                if(find(gr[i].begin(), gr[i].end(), j)==gr[i].end())
                {grt[i].push_back(j); gr[j].push_back(i);}
        }
    }
}

void afis_grafNou()
{
    int i,j;
    for(i=1; i<=nrc; i++)
    {
        for(j=0; j<gr[i].size(); j++)
        cout<<gr[i][j]<<" ";
    cout<<endl;
    } cout<<endl;
}


int main()
{
    int i,j,x,y;
    citire();
    tare_conex();
    fa_graful_componentelor();
    afis_grafNou();
    for(i=0; i<t.size(); i++)
    {
        x=t[i].first;
        y=t[i].second;
        nrmi=0;
        for(j=1; j<=nrc; j++)
            {
                //vad carei comp conexe ii apartine x si careia ii apartine y
                if(find(ctc[j].begin(), ctc[j].end(), x)!= ctc[j].end())
                c1=j;
                if(find(ctc[j].begin(), ctc[j].end(), y)!= ctc[j].end())
                c2=j;
            }
        //daca apartin aceleiasi nu inversez nicio muchie
        memset(use, 0, sizeof(use));
        ok=0;
        dfs_grafNou(c1);
        if(c1==c2 || ok)
            g<<nrmi<<'\n';
        else
            {
                memset(use, 0, sizeof(use));
                dfst_grafNou(c1);
                g<<nrmi<<'\n';
            }
    }
    f.close();
    g.close();
    return 0;
}