Блог пользователя wil93

A graph problem
Автор wil93, 15 лет назад, По-английски
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 ...

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

    • Проголосовать: нравится
    • +8
    • Проголосовать: не нравится

    15 лет назад, скрыть # |
     
    Проголосовать: нравится 0 Проголосовать: не нравится
    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 ?
    → Ответить
    15 лет назад, скрыть # |
    ← Rev. 2  
    Проголосовать: нравится 0 Проголосовать: не нравится
    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.

    → Ответить
    15 лет назад, скрыть # |
     
    Проголосовать: нравится 0 Проголосовать: не нравится
    Everyone seems to skip legend which is important this time ;)
    → Ответить