Category DFS

UVA – 10227 – Forests

Arunima Mandal 1 Comment

Problem Link: https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&category=0&problem=1168

Note: This problem is a Disjoint set problem, but a tricky one indeed. Here the main concern is to understand the input, and what input will be fed to the Disjoint set algorithm. We’ll have to understand what the opinion means patiently and carefully.

About the input format, we do not have to bother with the blank lines because “std::cin” by nature isn’t bothered with those blank lines. We’ll just have to make sure that we use getchar() before using getline() as there are some “cin” statements before using getline(). Please have a look at the following link for further explanation.

The following code is basically the disjoint set algorithm + the “graph” vector and the two for loops inside the main function.

So the purpose of those is to make the feasible input to be fed to the disjoint set algorithm. Now, for the sample input that is given in the problem statement:

1

3 4
1 2
3 3
1 3
2 2
3 2
2 4

Explanation of the code with respect to the above input:

I have considered a vector of sets named graph, where I am keeping track of which person has heard which set of trees. After processing the input, before running the two for loops, the above input seems like:

graph[1]={2,3}

graph[2]={2,4}

graph[3]={2,3}

Then in the two for loops, if the two person’s set matches, then I am making those two people as “connected” via the “Union” function. And lastly checking which of the people are connected or not.

**My two cents on this problem: In such kinds of problems, the key to thinking intuitively is – Ultimately we need to find out which type of group has to be connected(to apply the Union function) and has to be checked whether they are connected or not.

Code:

#include <bits/stdc++.h>

using namespace std;

int Find(int x, vector<int> &root)
{
    if(x==root[x]) return x;
    return root[x]=Find(root[x], root);
}

void Union(int x, int y, vector<int> &root, vector<int> &ranking)
{
    int rootX=Find(x, root);
    int rootY=Find(y, root);
    if(rootX!=rootY)
    {
        if(ranking[rootX]>=ranking[rootY])
        {
            root[rootY]=rootX;
            ranking[rootX]+=ranking[rootY];
        }
        else
        {
            root[rootX]=rootY;
            ranking[rootY]+=ranking[rootX];
        }
    }
}


int main()
{
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
    int t;
    cin>>t;

    while(t--)
    {
        int people, trees;
        cin>>people>>trees;

        vector<set<int> > graph(people+1);
        vector<int> root(people+1), ranking(people+1);

        for(int i=1; i<=people; i++)
        {
            root[i]=i;
            ranking[i]=1;
        }
        string s;

        getchar(); //Flushig the '\n' from the input buffer which was there for using cin

        while(getline(cin,s) && s.size())
        {
            size_t found=s.find(" ");
            string num1=s.substr(0, found);
            int x=stoi(num1);
            string num2=s.substr(found+1);
            int y=stoi(num2);

            graph[x].insert(y);

        }

        for(int i=1; i<=graph.size(); i++)
        {
            for(int j=i+1; j<=graph.size(); j++)
            {
                if(graph[i]==graph[j]) Union(i, j, root, ranking);
            }
        }

        int ans=0;
        for(int i=1; i<=people; i++)
        {
            if(root[i]==i) ans++;
        }
        cout<<ans<<endl;
        if(t) cout<<endl;
    }
    return 0;
}

UVA – 10178 – Count the Faces

Arunima Mandal 1 Comment

Problem link: https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1119

Note:

This problem mainly comprises one main concern – calculating the faces. Now there is already a famous formula – Euler’s formula for calculating the number of faces in a planar graph which is

{\displaystyle v-e+f=2.}

Here, v = total number of vertices of all the connected components of the planar graph

e = total number of edges of all the connected components of the planar graph

f = number of faces (regions bounded by edges, including the outer, infinitely large region) of the planar graph

Since we want the faces for this problem, the equation we should be looking for is:

f = 2 + e − v …………………………………………………………… (1)

Now, at this point it is seeming pretty easy to get the number of faces, right? Because we just need only the number of vertices and edges and nothing else!! But here goes the main concern – The above equation is assuming there is only one connected component in the planar graph. So if the overall graph is not connected, that means, if, in the plane, we are talking about multiple subgraphs that are disconnected from each other, then we’ll have to apply the above equation for each of the connected components to get the total number of faces, right?

But again, in that case (more than 1 connected component), there is another certain issue – the face counter for the outer region gets counted equal to the number of different connected component, which actually should be counted as 1.

For example: Suppose we are considering the below graphs as the input of our problem.

Here, in the plane, the number of connected components is 2 (A-B-C-D and E-F-G-H) and the above equation will generate the number of faces for each connected component as 2, so in total 4 faces for the graphs present in this plane. But the result should be 3 instead of 4.



So the thing is that, we should consider only 1 face for the enitre infinite outer region for all the different connected components. So the equation for our problem would be modified to:

f = ( e − v + number of connected components ) + 1 …………………………. (2)

This will be applicable because we can easily derive that, if we make summation of each connected component, then we can reach to the above equation for considering only 1 outer region for all the connected components present in the plane.

Now the solution to the problem comes down to the two following steps:

  1. Find out the number of connected components (/ number of cycles in the undirected graph) in the graph that is given to us
  2. Put that into the modified Euler’s equation (2) to get the result.

The first part of the solution can be solved in many different ways like DFS or Disjoint set. I have used the Disjoint set algorithm here.

Code:

#include <bits/stdc++.h>

using namespace std;

int Find(int x, vector<int> &root)
{
    if(x==root[x]) return x;
    return root[x]=Find(root[x], root); //Path compression
}

void Union(int x, int y, vector<int> &root, vector<int> &ranking)
{
    int rootX=Find(x, root);
    int rootY=Find(y, root);
    if(rootX!=rootY)
    {
        if(ranking[rootX]>=ranking[rootY])
        {
            root[rootY]=rootX;
            ranking[rootX]+=ranking[rootY];
        }
        else
        {
            root[rootX]=rootY;
            ranking[rootY]+=ranking[rootX];
        }
    }
}


int main()
{
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
    int node, edge;
    while(cin>>node>>edge)
    {
        vector<int> root(node+1), ranking(node+1);
        for(int i=1; i<=node; i++)
        {
            root[i]=i;
            ranking[i]=1;
        }
        unordered_map<char, int> ump;
        int c=0;
        for(int i=0; i<edge; i++)
        {
            char a,b;
            cin>>a>>b;
            if(!ump.count(a))
            {
                c++;
                ump[a]=c;
            }
            if(!ump.count(b))
            {
                c++;
                ump[b]=c;
            }

            int x=ump[a];
            int y=ump[b];
            Union(x, y, root, ranking);
        }

        int faces=0;
        for(int i=1; i<=node; i++)
        {
            if(root[i]==i) faces++;
        }
        cout<<(edge-node+faces)+1<<endl; //the +1 is for 1 infinite outer region
    }
    return 0;
}

Iterative DFS for Detecting Cycle in any Directed Graph

Arunima Mandal Leave a comment

Note:

The algorithm for detecting cycles in any directed graph is easier using recursive DFS. But Iterative DFS approach to detect a cycle is a bit complex and tricky. I have commented on the code where necessary to make the algorithm more understandable.

In any case, the time complexity of the algorithm is O(V+E). 

#include <bits/stdc++.h>

using namespace std;

#define MAX 100005

bool detectCycle(int nodes, vector<vector<int> >& adjList)
{
    if(nodes==1) return false;
    stack<int> st;
    bool on_stack[MAX+1]= {0};
    bool visited[MAX+1]= {0};
    for(int i=0; i<nodes; i++) //In case the graph is disconnected
    {
        if(visited[i]) continue; //For time efficiency
        st.push(i);
        while(!st.empty())
        {
            int u=st.top();
            if(!visited[u])
            {
                visited[u]=1;
                on_stack[u]=1;
            }
            else //backtracking, but keeping the visited array unchanged for time efficiency
            {
                on_stack[u]=0;
                st.pop();
                continue;
            }
            for(int j=0; j<adjList[u].size(); j++)
            {
                int v=adjList[u][j];
                if(!visited[v])
                {
                    st.push(v);
                }
                else
                {
                    if(on_stack[v]) return true; //cycle detected
                }
            }
        }
    }
    return false;
}


int main()
{
    vector<vector<int> > adjList(MAX+1);
    int nodes, edges;
    cout<<"Enter the number of nodes: ";
    cin>>nodes;
    cout<<endl;
    cout<<"Enter the number of edges: ";
    cin>>edges;
    cout<<endl;
    cout<<"Enter the pair of edges: "<<endl;
    for(int i=0; i<edges; i++)
    {
        int from, to;
        cin>> from>> to;
        adjList[from].push_back(to);
    }
    if(detectCycle(nodes, adjList)==1) cout<<"Cycle found!"<<endl;
    else cout<<"Cycle not found!"<<endl;
    return 0;
}

SPOJ – PT07Y – Is it a tree

Arunima Mandal 3 Comments

An undirected/directed graph is a tree if anyone know that any two of the following three properties are true:

1. It is connected
2. There are n – 1 edges, where n is the number of nodes
3. There are no cycles

It is better to check if all these three conditions are true, then that graph is surely a tree.
This problem also can be solved with BFS, but I used DFS because of smaller size of code n more simplyness than BFS.
Here, the source is not given so I have assumed the 1st node of the 1st given edge to be the source with the help of a variable x, you can assume any of the node.

#include <bits/stdc++.h>

#define pf                  printf
#define sf(a)               scanf("%d",&a)
#define sfl(a)              scanf("%lld",&a)
#define sff(a,b)            scanf("%d %d",&a,&b)
#define sffl(a,b)           scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)         scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)        scanf("%lld %lld %lld",&a,&b,&c)
#define sffff(a,b,c,d)      scanf("%d %d %d %d",&a,&b,&c,&d)
#define sffffl(a,b,c,d)     scanf("%lld %lld %lld %lld",&a,&b,&c,&d)
#define sfffff(a,b,c,d,e)   scanf("%d %d %d %d %d",&a,&b,&c,&d,&e)
#define sfffffl(a,b,c,d,e)  scanf("%lld %lld %lld %lld %lld",&a,&b,&c,&d,&e)
#define sfc(a)              scanf("%c",&a)
#define ms(a,b)             memset(a,b,sizeof(a))
#define pb(a)               push_back(a)
#define pbp(a,b)            push_back({a,b})
#define db                  double
#define ft                  float
#define ll                  long long
#define ull                 unsigned long long
#define ff                  first
#define ss                  second
#define sz(x)               x.size()
#define qu                  queue
#define pqu                 priority_queue
#define vc                  vector
#define vi                  vector<int>
#define vll                 vector<long long>
#define pii                 pair<int,int>
#define pis                 pair<int,string>
#define psi                 pair<string,int>
#define all(x)              x.begin(),x.end()
#define CIN                 ios_base::sync_with_stdio(0); cin.tie(0)
#define max3(a, b, c)       max(a, b) > max(b, c) ? max(a, b) : max(b, c)
#define min3(a, b, c)       min(a, b) < min(b, c) ? min(a, b) : min(b, c)
#define loop0(i,n)          for(int i=0;i<n;i++)
#define loopn(i,n)          for(int i=1;i<n;i++)
#define loop1(i,n)          for(int i=1;i<=n;i++)
#define loopi(i,n)          for(int i=0;i<n-1;i++)
#define loopab(i,a,b)       for(int i=a;i<=b;i++)
#define loopba(i,b,a)       for(int i=b;i>=a;i--)
#define REV(i,n)            for(i=n; i>=0; i--)
#define stlloop(x)          for(__typeof(x.begin()) it=x.begin();it!=x.end();it++)
#define gcd(a, b)           __gcd(a, b)
#define lcm(a, b)           ((a)*((b)/gcd(a,b)))
#define case1(z)            cout<<"Case "<<z<<": "
#define case2(z)            printf("Case %d: ",z)
#define PI                  3.14159265358979323846264338328
#define valid(tx,ty)        tx>=0 && tx<row && ty>=0 && ty<col
#define intlim              2147483648
#define MAX                 1000000
#define inf                 100000000

/*------------------------------Graph Moves----------------------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*---------------------------------------------------------------------*/

using namespace std;

vector<int>g[MAX+1];
bool visited[MAX+1];
int c,d;

void dfs(int u)
{
    visited[u]=1;
    for(int i=0; i<g[u].size(); i++)
    {
        int v=g[u][i];
        if(visited[v]) //Checking cycle/loop
        {
            d=1;
            break;
        }
        else
        {
            c++; // Checking connected
            dfs(v);
        }
    }
}
int main()
{
    CIN;
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int node,edge;
    cin>>node>>edge;
    int x=0,src;
    for(int i=0; i<edge; i++)
    {
        int from,to;
        cin>>from>>to;
        if(x==0) src=from;
        x=1;
        g[from].push_back(to);
    }

    c=1; // Either the graph is connected or not(Either each vertex is visited once or not)
    d=0; // For checking cycle/loop
    visited[src]=1;
    dfs(src);

    if(!d && c==node && edge==node-1) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return 0;
}

UVa – 280 – Vertex

Arunima Mandal Leave a comment 
#include <bits/stdc++.h>

#define ms(a,b)         memset(a,b,sizeof(a))
#define pb(a)           push_back(a)
#define db              double
#define ft              float
#define ll              long long
#define ull             unsigned long long
#define ff              first
#define ss              second
#define qu              queue
#define pqu             priority_queue
#define vc              vector
#define vi              vector<int>
#define vll             vector<long long>
#define pii             pair<int,int>
#define pis             pair<int,string>
#define psi             pair<string,int>
#define all(x)          x.begin(),x.end()
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define loop0(i,n)      for(int i=0;i<n;i++)
#define loop1(i,n)      for(int i=1;i<=n;i++)
#define stlloop0(i,x)   for(int i=0;i<x.size();i++)
#define stlloop1(x)     for(__typeof(x.begin()) it=x.begin();it!=x.end();it++)
#define gcd(a, b)       __gcd(a, b)
#define lcm(a, b)       ((a)*((b)/gcd(a,b)))
#define case(z,x)       cout<<"Case "<<i<<": "<<x<<endl
#define case(z)         cout<<"Case "<<z<<": "
#define PI              3.14159265358979323846264338328
#define valid(nx,ny) nx>=0 && nx<r && ny>=0 && ny<c
#define MAX             2000

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

using namespace std;

vector<int>g[MAX],ans;
bool visited[MAX];
int node;

void dfs(int u)
{
    int temp;
    for(int i=0; i<g[u].size(); i++)
    {
        temp=g[u][i];
        if(!visited[temp])
        {
            visited[temp]=1;
            dfs(temp);
        }
    }
}
int main()
{
    CIN;
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);

    while(cin>>node && node!=0)
    {
        int from,to;
        while(cin>>from && from!=0)
        {
            while(cin>>to && to!=0) g[from].pb(to);
        }
        int q;
        cin>>q;
        loop0(i,q)
        {
            int src;
            cin>>src;
            memset(visited,0,sizeof visited);
            dfs(src);
            int c=0;
            loop1(j,node)
            {
                if(visited[j]==0)
                {
                    c++;
                    ans.pb(j);
                }
            }
            cout<<c;
            stlloop0(k,ans) cout<<" "<<ans[k];
            cout<<endl;
            ans.clear();
        }
        loop0(i,MAX) g[i].clear();
    }
    return 0;
}