English

Transformation

Example Input(will be used in the explanation:

5 6

1 2
1 3
2 4
5 3
7 5
8 4

In this problem there are 2 group of conditions:

• 2nd group of conditions creates logic formulas with 2 literals and a disjunction (e.g. "3 7" means (3 or 7) -> (3v7)
• 1st group of conditions can also be used to bind Xth island with X+Nth island where choosing X+Nth island means that not choosing Xth island. Because of that we can change the meaning of numbers higher than N into meaning that its corresponding island isn't going to be chosen.(e.g. if N=5 and we have a condition "3 7" it will mean (3 or not 2) -> (3v-2)

After applying the above transformations to the example input our problem will become (1v2)∧(1v3)∧(2v4)∧(5v3)∧(-2v5)∧(-3v4). Now this problem has been transformed into an NP-complete problem called satisfaibility problem where the question asks us if there is a valid solution to the above logical form. But since there are only 2 literals in every disjunction group it is actually a special case of the satisfaibility problem called 2-SAT which is solvable in polynomial time.

There is a unique property of the 2-sat problem. One can use the Conditional Disjunction rule(ϕ V 𝜓 ≡ ~ϕ → 𝜓) to create a directed graph using given group of conditions. For example example input will create the below directed edges:

1 2:(1v2) :(-1→2),(-2→1)
1 3:(1v3) :(-1→3),(-3→1)
2 4:(2v4) :(-2→4),(-4→2)
5 3:(5v3) :(-5→3),(-3→5)
7 5:(-2v5):(2→5),(-5→-2)
8 4:(-3v4):(3→4),(-4→3)

Solution

Now we have a graph that will force the use of the 2nd group of rules. But to adhere to first group of rules we have to prove that there is a set where we choose exactly one island from each pair. But how will we prove this? This is where logic does its magic. Logical implication operator(→) has the transitivity property. This means that if (P→Q)∧(Q→R) is true then (P→R) is also true. So if there is a path in this graph from Xth node to Yth node then (X→Y) is true.

Now let's assume there is a path from node X to Node -X (X→-X) this means that if X is true -X is true. Since this can't be possible X can never be true and -X must hold. But what if there is a path from Xth node to -Xth node and a path from -Xth node to Xth node (X→-X)∧(-X→X)≡(-Xv-X)∧(XvX)≡(-X)∧(X). In this case there can never be a solution to this problem. That is why in this problem we need to look if there is a path from Xth vertex to -Xth vertex and vice versa for every X. If there are paths from both X to -X and -X to X for any X we say that there is no combination of islands. If there isn't then there can be 1 or multiple combinations of islands.

One can easily see that finding the group of islands can be done by using DFS/BFS N times until every island pair is checked. Since DFS takes O(V+E) or for our problem O(N+K) times the complexity of the problem will become O(N(N+K)). But there is a much better uproach using SCCs(Strongly Connected Components).

If there is a path form Ath vertex to Bth vertex and a path from Bth Vertex to Ath vertex there must be a cycle(SCC) that passes from both Ath and Bth vertexis. To find these Strongly connected components we need to do 2 DFS's only. In first DFS the algorithm has to search all nodes mark them as visited and save the time whenever its job is done with a node(using stack to save the vertex index also works). Before 2nd DFS we first reverse every edge of the graph and we once again take DFS but this time starting from the last node that was timed(or by popping the stack).While using the 2nd DFS we mark nodes as visited and color every node according to their group. This way at the end we can look at every Xth and -Xth node in O(1) time. If they are in the same SCC then there cannot be a solution.

Since DFS takes O(N+K) times and looking for N vertexes would take O(N) time in total the complexity becomes O(N+K) which is much better than O(N(N+K)).

Why does SCC algorithm work?

Lets assume we reached Y from X in first DFS by going through A B and C nodes: Y→A→B→C→X

After transforming this edges it will seem like this: Y←A←B←C←X

At first step we have to start from Y then start from A, B and C because of that, as you can see, the path in untransformed graph from Y to X is not usable anymore. But lets say there is another path in this transformed graph from Y to X(Y→X). This means that there is a path from X to Y in the initial graph (X→Y). Since (Y→A→B→C→X) ≡ (-X→X) also proves that there is a path from Y to X we can conclude that there is an SCC that contains vertexes X and Y.

Türkçe

Dönüşüm

Örnek Girdi(açıklamada kullanılacaktır):

5 6

1 2
1 3
2 4
5 3
7 5
8 4

Bu problemde 2 grup koşul vardır:

• 1. koşul grubu, 2 değişkenli bir disjunction(mantıksal veya işlemi) ile mantık formülleri oluşturucak (ör. "3 7", (3 veya 7) -> (3v7 anlamına gelir)
• 1. koşul grubu, X. adayı X+N. ada ile bağlamak için de kullanılabilir; burada X+N'inci adanın seçilmesi, X. adanın seçilmemesi anlamına gelir. Bu nedenle, N'den büyük sayıların anlamını, karşılık gelen adanın seçilmeyeceği anlamına değiştirebiliriz. (örn. N=5 ise ve koşul "3 7" adaları ise bu koşulu (3 veya 2 değil) -> (3v-2) şekline çevirebiliriz)

Yukarıdaki dönüşümleri örnek girdiye uyguladıktan sonra problemimiz (1v2)∧(1v3)∧(2v4)∧(5v3)∧(-2v5)∧(-3v4) olacaktır. Bu işlemlerden geçtikten sonra bu problem satisfiability problemi adı verilen NP-complete bir probleme dönüştürmüş oluyoruz ve soru bize yukarıdaki mantıksal forma geçerli bir çözüm olup olmadığını soruyor. Ancak her disjunction(veya) grubunda sadece 2 değişken olduğu için bu problem 2-SAT adı verilen ve polinomial zamanda çözülebilen satisfiability probleminin özel bir haline dönüştürmüş oluyoruz.

2-sat probleminin önemli bir özelliği vardır. Elimizdeki koşullar grubunu Conditional Disjunction kuralını kullanarak (ϕ V 𝜓 ≡ ~ϕ → 𝜓) sorunun çözümünde kullanacağımız bir directed graph oluşturabiliriz. Yukarda verdiğimiz örnek girdi aşağıdaki edgelere sahip bir graph oluturacaktır:

1 2:(1v2) :(-1→2),(-2→1)
1 3:(1v3) :(-1→3),(-3→1)
2 4:(2v4) :(-2→4),(-4→2)
5 3:(5v3) :(-5→3),(-3→5)
7 5:(-2v5):(2→5),(-5→-2)
8 4:(-3v4):(3→4),(-4→3)

Çözüm

Elimizdeki bu graph 2. kural grubunun kullanımını garanti altına alacak. Ancak birinci grup kurallara uymak için, her bir çiftten sadece bir ada seçtiğimiz bir küme olduğunu kanıtlamamız gerekiyor. Peki bunu nasıl kanıtlayacağız? İşte mantığın sihri burada ortaya çıkıyor. Mantıksal çıkarım operatörü(→) transitivity özelliğine(https://en.wikipedia.org/wiki/Transitive_relation) sahiptir. Bunun anlamı, eğer (P→Q)∧(Q→R) doğruysa, o zaman (P→R) de doğrudur. Yani bu grafikte X. node'dan Y. node'a bir yol varsa (X→Y) doğrudur.

Şimdi, X node'dan -X node'una (X→-X) bir yol olduğunu varsayalım, bu, X doğruysa -X de doğrudur demektir. Bu mümkün olamayacağı için X asla doğru olamaz ve -X'in doğru olması gerekir. Fakat ya X. node'dan -X. node'a bir yol varsa ve -X. node'dan X. node'a da bir yol varsa (X→-X)∧(-X→X)≡(-Xv-X)∧(XvX)≡( -X)∧(X). Bu durumda, bu probleme ait bir çözüm var olamaz. Bu yüzden 2-sat probleminde her X için X. node'dan -X. node'a ve tam tersi bir yol olup olmadığına kontrol ederiz. Herhangi bir X için hem X'ten -X'e hem de -X'ten X'e yollar varsa adalar kombinasyonu yoktur deriz ve algoritma son bulur, ama eğer yoksa, 1 veya birden fazla ada kombinasyonu olabilir deriz.

Her ada çifti kontrol edilene kadar DFS/BFS N kez kullanılarak adalar grubunun bulunabileceği kolayca görülebilir. DFS, O(V+E) veya problemimiz için O(N+K) zaman aldığından, problemin complexity'si O(N(N+K) olacaktır). Ancak SCC'leri (Strongly connected component) kullanarak çok daha hızlı bir çözüm bulabilirz.

A'nıncı node'dan B'ninci node'a bir yol ve B'ninci node'dan A'nıncı node'a bir yol varsa, hem A'nıncı hem de B'ninci düğümden geçen bir döngü (SCC) olmalıdır. SCC'leri(karşılıklı ulaşılabilir node gruplarını) bulmak için sadece 2 DFS yapmamız gerekiyor. İlk DFS'de graph'ın tüm node'ları araması ve bir node'la işimiz bittiğinde ziyaret edilmiş olarak işaretleyerek zamanlarını kaydetmesi gerekir (bu noktada zamanları kaydetmek için stack kullanılabilir). 2. DFS'den önce ilk önce grafiğin her kenarını tersine çeviririz ve bir kez daha DFS alırız, ancak bu sefer zamanlarına göre tersten ilerleriz (veya stack'ten çıkartarak). 2. DFS'yi kullanırken node'ları visited olarak işaretler ve her node'u grubuna göre renklendiririz. Bu adımdan sonra her node için(her X ve -X için) hangi SCC de olduğuna O(1) zamanda bakabiliriz. Aynı SCC'deyseler, o zaman bir çözüm olamaz.

DFS, O(N+K) zaman aldığından ve 2 DFS ile SCC gruplarını belirledikten sonra N düğümü kontrol etmek toplamda O(N) zaman alacağından, complexityi O(N+K)'ya düşürmüş oluruz.

SCC algoritması neden çalışıyor?

İlk DFS'de A B ve C node'larından geçerek X'ten Y'ye ulaştığımızı varsayalım: Y→A→B→C→X

Edge'leri ters çevirdikten sonra graph bu şekilde görünecek: Y←A←B←C←X

Ters çevirilmiş 2. Dfs'te Y'den başlayıp DFS alırız ve ulaştığımız her node'u visited olarak işaretleriz sonra da sırayla unvisited(uğranmamış) nodelardan tekrardan DFS başlatırız, bu örnekte Y den sonra sırayla A, B ve C'den başlamalıyız (bu adımda Y,A,B,C den başladığımızda sadece kendilerine ulaştığımız için sadece kendilerinden oluşan bir SCC'ye aitlerdir), çünkü gördüğünüz gibi, Y'den X'e dönüştürülmemiş grafikteki bu yollar artık kullanılamaz. Ama diyelim ki bu dönüştürülmüş graph'ta Y'den X'e(Y→X) başka bir yol var. Bu, ilk graph (X→Y) X'ten Y'ye bir yol olduğunu kanıtlar. (Y→A→B→C→X) ≡ (Y→X) de Y'den X'e bir yol olduğunu kanıtladığı için, X ve Y nodelarını içeren bir SCC olduğu sonucuna varabiliriz.

Code

#include <bits/stdc++.h>

using namespace std;

using namespace std;

struct graph{

    int n;      //element count
    vector<int> *nblistPos,*nblistNeg;
    bool *visitedPos,*visitedNeg;
    int *colorPos,*colorNeg;
    stack<int> endStack;

    bool& visited(int index){
        if(index>0)return visitedPos[index];
        return visitedNeg[-index];
    }
    vector<int>& nblist(int index){
        if(index>0)return nblistPos[index];
        return nblistNeg[-index];
    }
    int& color(int index){
        if(index>0)return colorPos[index];
        return colorNeg[-index];
    }

    graph(int x):n(x){
        nblistPos=new vector<int>[n+1];
        nblistNeg=new vector<int>[n+1];
        visitedPos=new bool[n+1];
        visitedNeg=new bool[n+1];
        colorPos=new int[n+1];
        colorNeg=new int[n+1];
        for(int i=1;i<=n;i++){
            visitedPos[i]=false;
            visitedNeg[i]=false;
        }
    }
    ~graph(){
        delete[] nblistPos;
        delete[] nblistNeg;
        delete[] visitedNeg;
        delete[] visitedPos;
        delete[] colorPos;
        delete[] colorNeg;
    }

    void addEdges(int a,int b){
        if(a>0)nblistPos[a].push_back(-b);
        else nblistNeg[-a].push_back(-b);
        if(b>0)nblistPos[b].push_back(-a);
        else nblistNeg[-b].push_back(-a);
    }


    void DFS1(int current){

        visited(current)=true;
        vector<int> &currentNBlist=nblist(current);

        for(int i=0;i<currentNBlist.size();i++){
            int next=currentNBlist[i];
            if(!visited(next)){
                DFS1(next);
            }
        }
        endStack.push(current);

    }

    void prepare(){

        vector<int> *templistPos=nblistPos;
        vector<int> *templistNeg=nblistNeg;
        nblistPos=new vector<int>[n+1];
        nblistNeg=new vector<int>[n+1];

        for(int i=1;i<=n;i++){
            for(int k=0;k<templistPos[i].size();k++){
                int next=templistPos[i][k];
                if(next>0)nblistPos[next].push_back(i);
                else nblistNeg[-next].push_back(i);
            }
        }
        delete[] templistPos;

        for(int i=1;i<=n;i++){
            for(int k=0;k<templistNeg[i].size();k++){

                int next=templistNeg[i][k];
                if(next>0)nblistPos[next].push_back(-i);
                else nblistNeg[-next].push_back(-i);
            }

        }

        delete[] templistNeg;

        for(int i=1;i<=n;i++){
            visitedNeg[i]=false;
            visitedPos[i]=false;
        }

    }
    void DFS2(){

        while(!endStack.empty()){
            int current=endStack.top();
            endStack.pop();
            if(!visited(current)){
                // cout<<"current "<<current<<endl;
                color(current)=current;
                DFS3(current,current);
            }
        }

    }

    void DFS3(int current,int COLOR){     //DFS 2 helper

        visited(current)=true;
        vector<int> &currentNBlist=nblist(current);

        for(int i=0;i<currentNBlist.size();i++){
            int next=currentNBlist[i];
            if(!visited(next)){
                color(next)=COLOR;
                DFS3(next,COLOR);
            }
        }

    }

};

int main(){    
    int N,K,x,y;
    cin>>N>>K;
    graph g(N);
    for(int i=0;i<K;i++){
        cin>>x>>y;
        if(x>N)x=N-x;       //if x=N+a -> x=-a
        if(y>N)y=N-y;
        g.addEdges(x,y);
    }

    for(int i=1;i<=N;i++){
        if(!g.visitedPos[i]){
            g.DFS1(i);
        }
        if(!g.visitedNeg[i]){
            g.DFS1(-i);
        }
    }

    g.prepare();
    g.DFS2();

    bool res=true;
    for(int i=1;i<=N;i++){
        // cout<<i<<" "<<g.colorPos[i]<<"<-->"<<g.colorNeg[i]<<endl;
        if(g.colorPos[i]==g.colorNeg[i]){
            res=false;
            break;
        }
    }
    switch(res){
        case false:
            cout<<"F"<<endl;
            break;
        case true:
            cout<<"T"<<endl;
            break;
    }
}