lalit.n.chandora's blog

Please someone help me with this problem "Love Triangle".
By lalit.n.chandora, history, 10 months ago, In English

So there's this question 939A - Love Triangle which has a tag of "graph" and I can't seem to find a solution for it. :( Although, the solution for this problem is available but it does not use graphs. I really wanted to know a solution which uses graph since it has a tag of "graph". Here's my approach for it 77461286

Here it checks for the number of vertices which has more than or equal to 3 occurences, if they are more than or equal to 3 then it prints YES. But, it fails on test 4. Please help.

 
 
 
 
  • Vote: I like it
  • -8
  • Vote: I do not like it

Comments Comments (5)
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

First of all, your approach is wrong when the graph is like a square. I suggest thinking that f(x) shows the special case of a directed graph. f(x) is the only one direct successor of x.

→ Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh, I was taking it as an undirected graph. Thanks a lot for pointing it out. :)

    → Reply
»
10 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

You can model almost any problem into a graph. This problem has the tag "Graph" which means it is solvable using graphs, but not necessarily that it is solvable only using graphs. Even problems that don't have the tag can probably be solved by modelling into a graph. The main idea required to solve a problem using graphs is to think "How can I model this into a graph". This problem being relatively simple, you can just check for a cycle using the code below.

Code

If you want to go all in, you can model the graph and then run a cycle detection algorithm for unweighted graphs.

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

here is my approach using graphs — 


#include<iostream>
#include<algorithm>
#define usi unsigned short int
#define ui unsigned int
#define ulli unsigned long long int
using namespace std;
int main()
{
//ios_base::sync_with_stdio(false);
//cin.tie(NULL);
//cout.tie(NULL);
usi n;
cin>>n;
usi a[n];
for(usi i=0;i<n;i++)
    cin>>a[i];

for(usi i=0;i<n;i++)
    {
        if( a[(a[(a[i]-1)]-1)] == i+1 )
            {
               cout<<"YES\n";
                goto x;
            }
    }
cout<<"NO\n";
x:
return 0;
}

`

→ Reply