wil93's blog

A graph problem
By wil93, 14 years ago, In English
I'm solving a problem from Italian Olympiad in Informatics, the statament says:

There is a secret organization. If you want to enter the organization you must find two members of the organization who will guarantee for you. You got N guys, and M relationships (i,j) between them. A relationship means that guy[i] guaranted for guy[j] (or vice-versa).

A "triad" is a triple (i,j,k) of guys such the relationships (i,j) (j,k) (k,i) exist.

You want to count how many triads are in the input file, that is formed as follows:

First line, M (relationships) and N (guys)
From 2 to M+1 each line has 2 integers (i,j) representing a relationship between i and j (or viceversa)

Output: the number of triads.

  •  1 ≤ N ≤ 100000.
  • N-1 ≤ M ≤ 2N-3.
  • 1 ≤ I, J ≤ N.

    • Sample input:
    13 8
4 2
8 3
1 2
8 5 
6 8
4 8
7 2
6 7
2 8
7 4
8 1
5 6
3 2
    Output:
    5

    Note: the order in which you consider a triad is irrelevant. In the sample we have the triad 2,4,7 that is the same as saying 4,7,2 ...

    - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

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

    Comments Comments (19)
    | Write comment?
    14 years ago, # |
      Vote: I like it 0 Vote: I do not like it
    My first approach was to use a map < int, set<int> > to get the relationship between (x,y) as follows:

    if ( mymap[x].find(y) != mymap.end() ) // then (x,y) exist

    I'm still convinced that this method should be ok, for the logaritmic search of set.

    So, for each guy (A), i try all his adjacent guys (B), and for each adjacent guy of B (guy C) i check if (C,A) exist.

    May this check be simplified in some way?

    Anyway the condition will be true for 2,4,7 but also for 4,2,7. So i thought "I'll make a set of the SUMS of triads indexes" like: myset.insert(a+b+c); // will not be performed if (a+b+c) is already in the set

    But in this way some diffirent triads were recognized equal. So i changed as follows:
    myset.insert(a+b+c+a*b*c);

    This gross method got 5/5 test cases (but the last test ran in 2,2 seconds while the limit was 2)

    - - - - - - - - - - -

    Then i made an observation: if a triad (x,y,z) exists, then my algorithm will find it exactly 6 times (disposition of 3 by 2 without repetition).

    Then instead of inserting everytime in the set, I made a simple count++ and at the end i made printf("%d",count/6);

    I was surprised when i saw that the new algorithm had the same execution time of the old one :(

    - - - - - - - - - - -

    Then I tried with the good old adjacency matrix, and it worked! Last test in 0,15 sec!
    But when running with a big N gets about 2GB of ram on my pc -.-''

    - - - - - - - - - - -

    After all, i noticed that the condition N ≤ 100000 is not applied (in the biggest test, N < 2000) so my program fit in time & memory. But the question is: how the hell is possible to fit with a big N ?
    → Reply
    • 14 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it
      Oh, and i have a little question: can I prove that having 6 integers (a,b,c) and (d,e,f) will never be true the condition (a+b+c+a*b*c) == (d+e+f+d*e*f)? Obviously assuming (d,e,f) isn't a permutation of (a,b,c)
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        No, there are many test exist that incorect for your rule:
        {(1,1,5) , (1,2,3)}. 
        you can write code to see all the test, like this:
        for (int i=1;i<=100;i++)
        for (int j=i;j<=100;j++)
        for (int z=j;z<=100;z++){
        int tmp= i+j+z + (i*j*z);
        if (mark[tmp]){
        printf ("%d %d %d\n%d %d %d\n//////////////\n", i,j,z, x[tmp],y[tmp],k[tmp]);
        }
        else{
        mark[tmp]= true;
        x[tmp]=i, y[tmp]=j, k[tmp]=z;
        }
        }

        ------------------------------
        for your main question, i think greedy algorithm can solve this.
        → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Oh that's true :)

          But in the main task we have

          (a≠b≠c) and (d≠e≠f)

          Couse nobody can guarantee for himself...

          Again, if this condition can fail (or cannot fail), would it be possible to find the mathematical proof of that?
          → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          I just found with your code {1,4,5} and {1,2,9} that fails my condition :(
          → Reply
          • 14 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            my code write many test not 2.
            here is a test that hold this condition:
            85 93 95
            79 97 98

            hope can help you
            → Reply
    14 years ago, # |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it
    Hi,

    I have this heuristic solution due to the sparse nature of the graph.

    Firstly, we compute the degrees of each vertex in the graph (in-degree + out-degree).

    If degree[x] <= 1, we know that we can reject x, as x will never form a triad.

    If degree[x] = 2, then we know that if x is in a triad, it can only be in one triad. So we can check whether x is in a triad and then delete it from the graph.

    If we do this simplification, we will eventually end in a situation where degree[x] >= 3 for all x. I think the worst case is if we do not delete any edges at all during this process (basically a complete graph followed by a lot of isolated vertices).

    Therefore, suppose the graph has K vertices left after we simplify the graph:

    2N - 3  = approximately K^2. That means we will have around sqrt(N) vertices left.

    If we use the K^3 algorithm now, the solution will be on the order of N*sqrt(N), which is about 32 million. I think this should run in time.

    If not, you can add in more heuristics. For example, you can run SCC and analyse each component separately. Maybe the transpose graph is even easier to analyse (This is assuming that (i,j) and (j,i) are both allowed. In that case, you are able to get a complete (or almost complete) undirected graph, so the transpose graph has very little edges). You can analyse the number of triads in the transpose graph. Suppose that is A. Then the answer is (K choose 3) - A.

    EDIT:

    Oops, I realised that it does not have to be a complete graph. All it needs to be is a 3-regular graph. That means there are still N/3 vertices left! :O.

    To solve this, I think we can keep removing vertices for degrees <= 10 for example, or until the remaining number of vertices is small enough. Then the preprocessing time will be around N * lg N * (10 choose 2) = 74 million, which should be small enough.

    In any case, this algorithm should work on randomly generated graphs, so this should give you a lot of marks :D. Maybe you will fail one or two testcases if you are unlucky.

    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Well, based on the way graph is created there always be vertex with degree <= 2 in each subgraph
      → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      The idea of calculating degree is formidable :)
      I'm going to try that :)
      → Reply
    14 years ago, # |
      Vote: I like it 0 Vote: I do not like it
    Everyone seems to skip legend which is important this time ;)
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Hi,

      May I know why you say that there will always be a vertex with degree <= 2 in each subgraph? Also, may I know what legend is skipped?
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Because there are no more then 2 edges to the guys that becomes part of mafia before given guy
        → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Sorry, I dont understand what you mean :(. Are you saying that there are no more than 2 edges pointing to the people who form the earliest possible mafia group, before anyone else joins?
          → Reply
          • 14 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            Let say it other way. Let's direct edges from guy, who invites to guy, who invited. Then there are no more then 2 incoming edges
            → Reply
            • 14 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it
              Oh, so you are saying that we draw edge from i to j with guy i guarantees guy j. Then indegree of any person x <= 2?

              Are you referring to this statement? "If you want to enter the organization you must find two members of the organization who will guarantee for you. "

              However, is it not possible that there are more than 2 people who can guarantee you, and you can choose any two?

              Just checking, if indegree of any person <= 2, is your solution to process the vertices one by one? Since indegree <= 2, the triads each vertex is in can be processed in at most 2 * D[x] time, where D[x] is the outdegree of vertex x. I think you would need some set or map to check for the edges efficiently, so the overall runtime is N lg N?

              → Reply
              • 14 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it
                Also we have to account that guys joined mafia one by one, so from any set of people one is the last and hadn't recommended anyone from this set to the mafia. Hence we will always find one with degree at most 2. Solution could be done in O(n) using hashset of edges and queue of vertices
                → Reply