【图论-图的连通性】有向图的强连通性

CNS_5t0_0r2 · 2024-06-15 11:04:22 · 算法·理论

前置知识

【0】一些定义

对于一个有向图，如果对于任意两点 u,v 存在从 u 到 v 的路径，那么将这张图称为强连通图。

一个有向图中的极大强连通图被称为强连通分量。

显然，环还是强连通图。

另外，一个点不可能在多个强连通图中。

【0.1】例子

例如，在这张图中：

有 3 个强连通分量：\{1,2,4\},\{3\},\{5\}。

既然环是强连通图，那么不难猜测强连通分量的判定肯定和环的判定有关。回顾无向图的双连通性，我们也可以猜测有向图的判定需要借助 dfn 和 low 数组。

但我们会发现一个问题，在无向图中只有树边和非树边的区别，在有向图中就没有这么简单了。

以这张图为例：

其中边有 4 种分类，如下图（这样的 DFS 生成树是有可能出现的）：

其中 dfn[6] = 5,dfn[5] = 6，其余的节点的 dfn 等于其节点编号。

接下来明确这 4 种边的定义：

树边的定义没变，就是 DFS 生成树的边。

前向边就是有向边 (u,v) 满足 u 在生成树上是 v 的祖先，后向边恰好相反，满足 v 在生成树上是 u 的祖先。

横叉边连接的点之间没有祖先和子孙的关系。

既然边的种类变多了，那么 low 数组的定义肯定也有变化。不过我们还没有对这 4 种边的性质（作用）进行分析，所以我们先不给出 low 数组的定义。

不过，low 数组的含义是没有变的，都是走若干边能回到的 dfn 最小的节点，只是因为边变了，所以走哪些边也会变。

【1】SCC 的求法

【1.1】4 种边的性质（作用）

树边不用说，没有它就不用谈如何判定环了。

前向边毛用没有。因为在 DFS 生成树上本来就有连接祖先和子孙的路径。如果前向边能形成环，那么这条路径肯定也能。

后向边很有用，因为它会和若干树边形成环。

横叉边很恶心，有的时候会，有的时候不会（在本图中会，但构造一个不会的例子应该是很简单的）。

【1.2】如何利用 4 种边

对于树边，很简单，在 DFS 中被遍历到的边就是树边。

对于如何区分前向边和后向边，我们不能向无向图一样通过判定是否被遍历确定祖先-子孙的关系。但是从 v-DCC 的缩点中，我们得到启发——

我们可以用一个栈来判断祖先和子孙的关系。

和 v-DCC 的求法类似，栈中的节点有如下性质：

如果子孙节点 u 在栈中，那么祖先节点 v 肯定在栈中。
进一步，我们得到：(u,v) 是后向边的必要条件是 v 在栈中。
在任意时刻，同一个 SCC 内的节点在栈中一定是连续的。又因为不管 low 数组定义怎么改一个节点肯定能回到自己（low[u] = dfn[u]），所以这样的节点是 SCC 深度最小的节点。这意味着，SCC 从栈中弹出的方式和 v-DCC 一模一样。

【1.3】low 数组的定义和求法

未完待续（逃）

【1.4】完整代码

const int N = 1e4 + 9,M = 5e4 + 9;
int n,m;
struct edge{
    int to,nex;
} e[M];
int head[N],ecnt;
void addedge(int u,int v){
    ecnt++;
    e[ecnt] = (edge){v,head[u]};
    head[u] = ecnt;
}
int dfn[N],low[N],id;
int cnt,bel[N];//cnt:强连通分量的个数。bel[u]:节点 u 所属的强连通分量编号
stack<int> s;
bool in_stack[N];//in_stack[u]:u是否在栈中
void dfs(int u){
    id++;
    dfn[u] = low[u] = id;
    s.push(u);
    in_stack[u] = true;
    for(int i = head[u];i;i = e[i].nex){
        int v = e[i].to;
        if(!dfn[v]){
            dfs(v);
            low[u] = min(low[u],low[v]);
        }
        else if(in_stack[v])
            low[u] = min(low[u],dfn[v]);
    }
    if(low[u] == dfn[u]){
        cnt++;
        int v;
        while(1){
            int v = s.top();
            s.pop();
            in_stack[v] = false;
            bel[v] = cnt;
            if(v == u)
                break;
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i = 1;i <= m;i++){
        int u,v;
        cin >> u >> v;
        addedge(u,v);
    }
    for(int i = 1;i <= n;i++)
        if(!dfn[i])
            dfs(i);
    return 0;
}

例题1：The Cow Prom S

非常板子的一道题。

额外维护一个 siz 数组，siz[i] 表示第 i 个 SCC 的节点数量。当遇到 dfn[u] = low[u] 的时候，将 SCC 的个数 cnt 加 1 并将这个 SCC 从栈中弹出，每弹出一个节点就将 siz[cnt] 加 1，最后扫描有多少个 siz[i] 大于 1 即可。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 9,M = 5e4 + 9;
int n,m,ans;
struct edge{
    int to,nex;
} e[M];
int head[N],ecnt;
void addedge(int u,int v){
    ecnt++;
    e[ecnt] = (edge){v,head[u]};
    head[u] = ecnt;
}
int dfn[N],low[N],id;
int cnt,siz[N],bel[N];
stack<int> s;
bool in_stack[N];
void dfs(int u){
    id++;
    dfn[u] = low[u] = id;
    s.push(u);
    in_stack[u] = true;
    for(int i = head[u];i;i = e[i].nex){
        int v = e[i].to;
        if(!dfn[v]){
            dfs(v);
            low[u] = min(low[u],low[v]);
        }
        else if(in_stack[v])
            low[u] = min(low[u],dfn[v]);
    }
    if(low[u] == dfn[u]){
        cnt++;
        int v;
        while(1){
            int v = s.top();
            s.pop();
            in_stack[v] = false;
            bel[v] = cnt;
            siz[cnt]++;
            if(v == u)
                break;
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i = 1;i <= m;i++){
        int u,v;
        cin >> u >> v;
        addedge(u,v);
    }
    for(int i = 1;i <= n;i++)
        if(!dfn[i])
            dfs(i);
    for(int i = 1;i <= cnt;i++)
        ans += siz[i] > 1;
    cout << ans;
    return 0;
}

【2】SCC 的缩点

类似 e-DCC 的缩点，我们把 SCC 缩点后会得到一个 DAG，这样就能用拓扑排序进行动态规划了。

缩点的方法和 e-DCC 是类似的（回顾【0】中强调的 SCC 的重要性质，一个点不可能在多个强连通图中），我们枚举所有的有向边 (u,v)，如果 u,v 不在一个 SCC 中（即 bel[u] \neq bel[v]），则在一个新图中连一条有向边 (bel[u],bel[v])。

因为是有向图，所以不能向无向图一样通过找反向边来确定边的起点，不过我们可以在链式前向星中的edge 结构体中存储起点，再微调 addedge 函数即可。

【2.1】代码实现

struct Graph{
    struct edge{
        int from,to,nex;
    } e[M];
    int head[N],ecnt;
    void addedge(int u,int v){
        ecnt++;
        e[ecnt] = (edge){u,v,head[u]};
        head[u] = ecnt;
    }
    void clear(){
        ecnt = 0;
        memset(head,0,sizeof head);
    }
} G1,G2;//G1是原图，G2是缩点后的图

int dfn[N],low[N],id;
int cnt,siz[N],bel[N];
stack<int> s;
bool in_stack[N];

void dfs(int u){
    id++;
    dfn[u] = low[u] = id;
    s.push(u);
    in_stack[u] = true;
    for(int i = G1.head[u];i;i = G1.e[i].nex){
        int v = G1.e[i].to;
        if(!dfn[v]){
            dfs(v);
            low[u] = min(low[u],low[v]);
        }
        else if(in_stack[v])
            low[u] = min(low[u],dfn[v]);
    }
    if(low[u] == dfn[u]){ 
        cnt++;
        int v;
        while(1){
            int v = s.top();
            s.pop();
            in_stack[v] = false;
            bel[v] = cnt;
            siz[cnt]++;
            val[cnt] += a[v];
            if(v == u)
                break;
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i = 1;i <= n;i++)
        cin >> a[i];
    for(int i = 1;i <= m;i++){
        int u,v;
        cin >> u >> v;
        G1.addedge(u,v);
    }
    for(int i = 1;i <= n;i++)
        if(!dfn[i])
            dfs(i);

    for(int i = 1;i <= m;i++){
        int u = G1.e[i].from,v = G1.e[i].to;
        if(bel[u] != bel[v]){
            G2.addedge(bel[u],bel[v]);
            deg[bel[v]]++;
        }
    }
    return 0;
}

例题 1：缩点

显然，如果一个子图 G = <V,E> 中所有点均可互相到达，因为 a_i 非负，所以在这个子图中答案即为 \sum_{u \in V} a_u。这种图在原图中不就是 SCC 吗！

所以，我们对原图进行缩点，每个点的点权即为原图中对应 SCC 中所有点的点权之和。

考虑缩点后得到的 DAG，这就是一个图上的 DP 问题，用拓扑排序就解决了。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 9,M = 1e5 + 9;
int n,m,ans,tot;
struct Graph{
    struct edge{
        int from,to,nex;
    } e[M];
    int head[N],ecnt;
    void addedge(int u,int v){
        ecnt++;
        e[ecnt] = (edge){u,v,head[u]};
        head[u] = ecnt;
    }
    void clear(){
        ecnt = 0;
        memset(head,0,sizeof head);
    }
} G1,G2;//G1是原图，G2是缩点后的图

int dfn[N],low[N],id;
int cnt,siz[N],bel[N];
stack<int> s;
bool in_stack[N];
int deg[N];//deg[i]：第i个SCC缩点后的入度

int a[N],val[N]; 
void dfs(int u){
    id++;
    dfn[u] = low[u] = id;
    s.push(u);
    in_stack[u] = true;
    for(int i = G1.head[u];i;i = G1.e[i].nex){
        int v = G1.e[i].to;
        if(!dfn[v]){
            dfs(v);
            low[u] = min(low[u],low[v]);
        }
        else if(in_stack[v])
            low[u] = min(low[u],dfn[v]);
    }
    if(low[u] == dfn[u]){ 
        cnt++;
        int v;
        while(1){
            int v = s.top();
            s.pop();
            in_stack[v] = false;
            bel[v] = cnt;
            siz[cnt]++;
            val[cnt] += a[v];
            if(v == u)
                break;
        }
    }
}

queue<int> q;
int dp[N];
void topsort(){
    for(int i = 1;i <= cnt;i++)
        if(deg[i] == 0){
            q.push(i);
            dp[i] = val[i];
        }

    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(int i = G2.head[u];i;i = G2.e[i].nex){
            int v = G2.e[i].to;
            deg[v]--;
            dp[v] = max(dp[v],dp[u] + val[v]);
            if(deg[v] == 0)
                q.push(v);
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i = 1;i <= n;i++)
        cin >> a[i];
    for(int i = 1;i <= m;i++){
        int u,v;
        cin >> u >> v;
        G1.addedge(u,v);
    }
    for(int i = 1;i <= n;i++)
        if(!dfn[i])
            dfs(i);

    for(int i = 1;i <= m;i++){
        int u = G1.e[i].from,v = G1.e[i].to;
        if(bel[u] != bel[v]){
            G2.addedge(bel[u],bel[v]);
            deg[bel[v]]++;
        }
    }

    topsort();

    for(int i = 1;i <= cnt;i++)
        ans = max(ans,dp[i]);
    cout << ans << '\n';
    return 0;
}

例题 2：The Largest Clique

显然，SCC 是满足题目条件的结点集，所以我们还是对原图缩点。

考虑缩点后得到的 DAG，要求任意两个结点 u,v 满足 u 可以到达 v 或 v 可以到达 u，满足条件的点集显然是 DAG 上的一条路径。

另外，我们希望这个点集尽可能大，这个问题几乎和上一题一模一样（甚至是弱化了的），只是所有点的点权为 1。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 9,M = 5e4 + 9;
int n,m,ans,tot;
struct Graph{
    struct edge{
        int from,to,nex;
    } e[M];
    int head[N],ecnt;
    void addedge(int u,int v){
        ecnt++;
        e[ecnt] = (edge){u,v,head[u]};
        head[u] = ecnt;
    }
    void clear(){
        ecnt = 0;
        memset(head,0,sizeof head);
    }
} G1,G2;

int dfn[N],low[N],id;
int cnt,siz[N],bel[N];
stack<int> s;
bool in_stack[N];
int deg[N];//deg[i]：第i个强连通分量缩点后的入度 
void dfs(int u){
    id++;
    dfn[u] = low[u] = id;
    s.push(u);
    in_stack[u] = true;
    for(int i = G1.head[u];i;i = G1.e[i].nex){
        int v = G1.e[i].to;
        if(!dfn[v]){
            dfs(v);
            low[u] = min(low[u],low[v]);
        }
        else if(in_stack[v])
            low[u] = min(low[u],dfn[v]);
    }
    if(low[u] == dfn[u]){
        cnt++;
        int v;
        while(1){
            int v = s.top();
            s.pop();
            in_stack[v] = false;
            bel[v] = cnt;
            siz[cnt]++;
            if(v == u)
                break;
        }
    }
}

queue<int> q;
int dp[N];
void topsort(){
    for(int i = 1;i <= cnt;i++)
        if(deg[i] == 0){
            q.push(i);
            dp[i] = siz[i];
        }

    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(int i = G2.head[u];i;i = G2.e[i].nex){
            int v = G2.e[i].to;
            deg[v]--;
            dp[v] = max(dp[v],dp[u] + siz[v]);
            if(deg[v] == 0)
                q.push(v);
        }
    }
}

void clear(){//多测不清空，爆零两行泪
    ans = 0;id = 0;
    G1.clear();
    G2.clear();
    while(!q.empty())
        q.pop();
    memset(dfn,0,sizeof dfn);
    memset(low,0,sizeof low);
    memset(siz,0,sizeof siz);
    memset(in_stack,0,sizeof in_stack);
    memset(bel,0,sizeof bel);
    memset(deg,0,sizeof deg);
    memset(dp,-1,sizeof dp);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        clear();
        cin >> n >> m;
        for(int i = 1;i <= m;i++){
            int u,v;
            cin >> u >> v;
            G1.addedge(u,v);
        }
        for(int i = 1;i <= n;i++)
            if(!dfn[i])
                dfs(i);

        for(int i = 1;i <= m;i++){
            int u = G1.e[i].from,v = G1.e[i].to;
            if(bel[u] != bel[v]){
                G2.addedge(bel[u],bel[v]);
                deg[bel[v]]++;
            }
        }

        topsort();

        for(int i = 1;i <= cnt;i++)
            ans = max(ans,dp[i]);
        cout << ans << '\n';
    }
    return 0;
}

例题 3：最优贸易

缩点，建出新图后建出反图，去掉所有在原图（缩点前）上不能到达 n 的点，然后 DP。

先维护每个 SCC 内的最大值和最小值，设 dp1_i 表示在第 i 个 SCC 内卖出的最大价值，dp2_i 为第 1 个 SCC 到第 i 个 SCC 的最小值，显然 dp1_i 等于第 i 个 SCC 内的最大值减 dp2_i，dp2_i 的求法也是简单的。

事实上 dp1,dp2 两个数组根本不需要，详见代码。

当然将原图上不能到达源点的点有更简单的方法，详见下一题。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9,M = 5e5 + 9;
int n,m,ans;
struct Graph{
    struct edge{
        int from,to,nex;
    } e[M << 1];
    int head[N],ecnt;
    void addedge(int u,int v){
        ecnt++;
        e[ecnt] = (edge){u,v,head[u]};
        head[u] = ecnt;
    }
    void clear(){
        ecnt = 0;
        memset(head,0,sizeof head);
    }
} G1,G2,G3;

int dfn[N],low[N],id;
int cnt,bel[N];
stack<int> s;
bool in_stack[N];
int in_deg[N],out_deg[N];

int a[N];
int val1[N],val2[N];//最大值，最小值

void dfs(int u){
    id++;
    dfn[u] = low[u] = id;
    s.push(u);
    in_stack[u] = true;
    for(int i = G1.head[u];i;i = G1.e[i].nex){
        int v = G1.e[i].to;
        if(!dfn[v]){
            dfs(v);
            low[u] = min(low[u],low[v]);
        }
        else if(in_stack[v])
            low[u] = min(low[u],dfn[v]);
    }
    if(low[u] == dfn[u]){
        cnt++;
        int v;
        while(1){
            int v = s.top();
            s.pop();
            in_stack[v] = false;
            bel[v] = cnt;
            val1[cnt] = max(val1[cnt],a[v]);
            val2[cnt] = min(val2[cnt],a[v]);
            if(v == u)
                break;
        }
    }
}

queue<int> q;
bool del[N];

void topsort(){
    for(int i = 1;i <= cnt;i++)
        if(out_deg[i] == 0){
            q.push(i);
        }

    while(!q.empty()){
        int u = q.front();
        q.pop();
        if(u != bel[n])
            del[u] = true;
        else
            continue;
        for(int i = G3.head[u];i;i = G3.e[i].nex){
            int v = G3.e[i].to;
            if(v != bel[n])
                out_deg[v]--;
            if(out_deg[v] == 0)
                q.push(v);
        }
    }
    //上述代码的作用是将无法到达n的所有点去掉
    q.push(bel[1]);
    ans = max(ans,val1[bel[1]] - val2[bel[1]]);

    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(int i = G2.head[u];i;i = G2.e[i].nex){
            int v = G2.e[i].to;
            if(del[v])
                continue;
            in_deg[v]--;
            val2[v] = min(val2[v],val2[u]);
            ans = max(ans,val1[v] - val2[v]);
            if(in_deg[v] == 0)
                q.push(v);
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    memset(val1,-1,sizeof val1);
    memset(val2,0x7f,sizeof val2);
    cin >> n >> m;
    for(int i = 1;i <= n;i++)
        cin >> a[i];
    for(int i = 1;i <= m;i++){
        int u,v,type;
        cin >> u >> v >> type;
        if(type == 1)
            G1.addedge(u,v);
        else{
            G1.addedge(u,v);
            G1.addedge(v,u);
        }
    }
    for(int i = 1;i <= n;i++)
        if(!dfn[i])
            dfs(i);

    for(int i = 1;i <= G1.ecnt;i++){
        int u = G1.e[i].from,v = G1.e[i].to;
        if(bel[u] != bel[v]){
            G2.addedge(bel[u],bel[v]);
            G3.addedge(bel[v],bel[u]);
            in_deg[bel[v]]++;
            out_deg[bel[u]]++;
        }
    }

    topsort();

    cout << ans << '\n';
    return 0;
}

例题 4：Professor Szu

显然一个 SCC 如果有多个点或者有自环那么其内部有 \inf 条路线，否则只有 1 条，考虑缩点。

缩点后建反图跑 DP，转移如下：

对于一个 SCC u，如果在反图上存在边 (u,v)，那么分两类讨论：

否则 dp_v = \inf。

跑 DP 前需要删除从 n + 1 所在强连通分量无法到达的点。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 9,M = 1e6 + 9,INF = 36501;
int n,m,ans;
struct Graph{
    struct edge{
        int from,to,nex;
    } e[M];
    int head[N],ecnt;
    void addedge(int u,int v){
        ecnt++;
        e[ecnt] = (edge){u,v,head[u]};
        head[u] = ecnt;
    }
    void clear(){
        ecnt = 0;
        memset(head,0,sizeof head);
    }
} G1,G2;

int dfn[N],low[N],id;
int cnt,siz[N],bel[N];
stack<int> s;
bool in_stack[N];
int val[N];//有自环的点权值为2，否则为1
int deg[N];//deg[i]：第i个强连通分量的入度

void dfs(int u){
    id++;
    dfn[u] = low[u] = id;
    s.push(u);
    in_stack[u] = true;
    for(int i = G1.head[u];i;i = G1.e[i].nex){
        int v = G1.e[i].to;
        if(!dfn[v]){
            dfs(v);
            low[u] = min(low[u],low[v]);
        }
        else if(in_stack[v])
            low[u] = min(low[u],dfn[v]);
    }
    if(low[u] == dfn[u]){
        cnt++;
        int v;
        while(1){
            int v = s.top();
            s.pop();
            in_stack[v] = false;
            bel[v] = cnt;
            siz[cnt] += val[v];
            if(v == u)
                break;
        }
    }
}

bool vis[N];
void dfs2(int u){
    vis[u] = true;
    for(int i = G2.head[u];i;i = G2.e[i].nex){
        int v = G2.e[i].to;
        deg[v]++;
        if(!vis[v])
            dfs2(v);
    }
}

queue<int> q;
int dp[N];
void topsort(){
    q.push(bel[n + 1]);
    dp[bel[n + 1]] = siz[bel[n + 1]] == 1 ? 1 : INF;

    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(int i = G2.head[u];i;i = G2.e[i].nex){
            int v = G2.e[i].to;
            deg[v]--;
            dp[v] = siz[v] == 1 ? min(dp[v] + dp[u],INF) : INF;
            if(deg[v] == 0)
                q.push(v);
        }
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i = 1;i <= n + 1;i++)
        val[i] = 1;
    for(int i = 1;i <= m;i++){
        int u,v;
        cin >> u >> v;
        if(u == v)
            val[u] = 2;
        G1.addedge(u,v);
    }
    for(int i = 1;i <= n;i++)
        if(!dfn[i])
            dfs(i);

    for(int i = 1;i <= m;i++){
        int u = G1.e[i].from,v = G1.e[i].to;
        if(bel[u] != bel[v])
            G2.addedge(bel[v],bel[u]);
    }

    dfs2(bel[n + 1]);

    topsort();

    for(int i = 1;i <= cnt;i++)
        ans = max(ans,dp[i]);
    vector<int> ans_seq;
    if(ans >= INF){
        cout << "zawsze\n";
        for(int i = 1;i <= n + 1;i++)
            if(dp[bel[i]] >= INF)
                ans_seq.push_back(i);
        int siz = ans_seq.size();
        cout << siz << '\n';
        for(int i = 0;i < siz;i++)
            cout << ans_seq[i] << ' ';
    }
    else{
        cout << ans << '\n';
        for(int i = 1;i <= n + 1;i++)
            if(dp[bel[i]] == ans)
                ans_seq.push_back(i);
        int siz = ans_seq.size();
        cout << siz << '\n';
        for(int i = 0;i < siz;i++)
            cout << ans_seq[i] << ' ';
    }
    return 0;
}

例题 5：糖果

由差分约束的思路，本题应该如下建边：

至于为什么要从小到大连边，是因为本题星星的亮度只有下界，我们只能有亮度小的恒星推亮度大的恒星。

然后跑最长路，如果有长度为正的环就无解。

不过本题卡 SPFA，分析发现本题的边权只有 0 和 1，考虑缩点。

对于一个 SCC，内部的边权应该均为 0，即改 SCC 内的所有恒星亮度相等，否则会得到矛盾（输出 -1）。

然后在得到的 DAG 上跑最长路，每个 SCC 内的所有点的最小亮度为 DAG 上到 SCC 的最短路 +1 ，每个 SCC 的贡献即这个值乘上 SCC 的大小。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 9,M = 1e5 + 9;
int n,m;
int op,u,v,w;
struct Graph{
    struct edge{
        int from,to,cost,nex;
    } e[M << 1];
    int head[N],ecnt;
    int cnt[N];
    void addedge(int u,int v,int w){
        ecnt++;
        e[ecnt] = (edge){u,v,w,head[u]};
        head[u] = ecnt;
    }
} G1,G2;
int dfn[N],low[N],id;
int cnt,siz[N],bel[N];
stack<int> s;
bool in_stack[N];
void dfs(int u){
    id++;
    dfn[u] = low[u] = id;
    s.push(u);
    in_stack[u] = true;
    for(int i = G1.head[u];i;i = G1.e[i].nex){
        int v = G1.e[i].to;
        if(!dfn[v]){
            dfs(v);
            low[u] = min(low[u],low[v]);
        }
        else if(in_stack[v])
            low[u] = min(low[u],dfn[v]);
    }
    if(low[u] == dfn[u]){
        cnt++;
        while(1){
            int v = s.top();
            s.pop();
            in_stack[v] = false;
            bel[v] = cnt;
            siz[cnt]++;
            if(v == u)
                break;
        }
    }
}
int deg[N];
queue<int> q;
int dp[N],ans;
void topsort(){
    for(int i = 1;i <= n;i++){
        if(deg[i] == 0){
            q.push(i);
            dp[i] = 1;
        }
    }
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(int i = G2.head[u];i;i = G2.e[i].nex){
            int v = G2.e[i].to,w = G2.e[i].cost;
            deg[v]--;
            dp[v] = max(dp[v],dp[u] + w);
            if(deg[v] == 0)
                q.push(v);
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i = 1;i <= m;i++){
        cin >> op >> u >> v;
        if(op == 1){
            G1.addedge(u,v,0);
            G1.addedge(v,u,0);
        }
        else if(op == 2)
            G1.addedge(u,v,1);
        else if(op == 3)
            G1.addedge(v,u,0);
        else if(op == 4)
            G1.addedge(v,u,1);
        else if(op == 5)
            G1.addedge(u,v,0);
        if(!(op & 1) && u == v){
            cout << -1;
            return 0;
        }
    }
    for(int i = 1;i <= n;i++)
        if(!dfn[i])
            dfs(i);
    for(int i = 1;i <= G1.ecnt;i++){
        int u = G1.e[i].from,v = G1.e[i].to,w = G1.e[i].cost;
        if(bel[u] == bel[v]){
            if(w == 1){
                cout << -1;
                return 0;
            }
        }
        else{
            G2.addedge(bel[u],bel[v],w);
            deg[bel[v]]++;
        }
    }
    topsort();
    for(int i = 1;i <= cnt;i++)
        ans += siz[i] * dp[i];
    cout << ans;
    return 0;
}