compro-library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub ningenMe/compro-library

:heavy_check_mark: test/graph/StronglyConnectedComponents-1.test.cpp

Depends on

Code

#define PROBLEM "https://yukicoder.me/problems/no/1023"

#include <vector>
#include <iostream>
#include <numeric>
#include <algorithm>
#include <stack>
using namespace std;
#include "../../lib/41-union-find-tree/UnionFindTree.cpp"
#include "../../lib/40-graph/StronglyConnectedComponents.cpp"

int main(){
    int N,M; cin >> N >> M;
    vector<pair<int,int>> edge;
    vector<pair<int,int>> bedge;
    for(int i = 0; i < M; ++i) {
        int a,b; cin >> a >> b;
        a--,b--;
        int c; cin >> c;
        if(c==1){
            bedge.push_back({a,b});
        }
        else{
            edge.push_back({a,b});
        }
    }
    UnionFindTree uf(N);
    for(auto& e:bedge){
        int a = e.first,b = e.second;
        if(uf.connected(a,b)){
            cout << "Yes" << endl;
            return 0;
        }
        uf.merge(a,b);
    }
    StronglyConnectedComponents scc(N);
    for(auto& e:edge){
        int a = e.first,b = e.second;
        if(uf.connected(a,b)){
            cout << "Yes" << endl;
            return 0;
        }
        scc.make_edge(uf[a],uf[b]);
    }
    scc.solve();
    vector<int> cnt(N,0);
    for(int i = 0; i < N; ++i) cnt[scc[i]]++;
    for(int i = 0; i < N; ++i) if(cnt[i] > 1){
        cout << "Yes" << endl;
        return 0;
    }
    cout << "No" << endl; 
    return 0;
}
#line 1 "test/graph/StronglyConnectedComponents-1.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/1023"

#include <vector>
#include <iostream>
#include <numeric>
#include <algorithm>
#include <stack>
using namespace std;
#line 1 "lib/41-union-find-tree/UnionFindTree.cpp"
/*
 * @title UnionFindTree - Union Find Tree
 * @docs md/union-find-tree/UnionFindTree.md
 */
class UnionFindTree {
    vector<int> parent,maxi,mini;
    inline int root(int n) {
        return (parent[n]<0?n:parent[n] = root(parent[n]));
    }
public:
    UnionFindTree(const int N = 1) : parent(N,-1),maxi(N),mini(N){
        iota(maxi.begin(),maxi.end(),0);
        iota(mini.begin(),mini.end(),0);
    }
    inline bool connected(const int n, const int m) {
        return root(n) == root(m);
    }
    inline void merge(int n,int m) {
        n = root(n);
        m = root(m);
        if (n == m) return;
        if(parent[n]>parent[m]) swap(n, m);
        parent[n] += parent[m];
        parent[m] = n;
        maxi[n] = std::max(maxi[n],maxi[m]);
        mini[n] = std::min(mini[n],mini[m]);
    }
    inline int min(const int n) {
        return mini[root(n)];
    }
    inline int max(const int n) {
        return maxi[root(n)];
    }
    inline int size(const int n){
        return (-parent[root(n)]);
    }
    inline int operator[](const int n) {
        return root(n);
    }
    inline void print() {
        for(int i = 0; i < parent.size(); ++i) cout << root(i) << " ";
        cout << endl;
    }
};
#line 1 "lib/40-graph/StronglyConnectedComponents.cpp"
/*
 * @title StronglyConnectedComponents - 強連結成分分解
 * @docs md/graph/StronglyConnectedComponents.md
 */
class StronglyConnectedComponents{
    int num,is_2sat,half,max_id,cnt;
    vector<vector<int>> edge;
    vector<int> label,order,low;
    stack<size_t> st;
    inline int rev(int i) { return i < half ? i + half : i - half; }
    inline void dfs(int& from) {
        low[from]=order[from]=cnt++;
        st.push(from);
        for(int& to:edge[from]) {
            if(order[to]==-1) {
                dfs(to);
                low[from]=min(low[from],low[to]);
            }
            else {
                low[from]=min(low[from],order[to]);
            }
        }
        if (low[from] == order[from]) {
            while(st.size()) {
                int u = st.top();st.pop();
                order[u] = num;
                label[u] = max_id;
                if (u == from) break;
            }
            max_id++;
        }
    }
public:
    StronglyConnectedComponents(const int n, bool is_2sat=0):num(n),max_id(0),cnt(0),is_2sat(is_2sat){
        if(is_2sat) num<<=1;
        edge.resize(num);
        label.resize(num);
        order.resize(num,-1);
        low.resize(num);
        half=(num>>1);
    }
    inline int operator[](int idx) {
        return label[idx];
    }
    inline void make_edge(const int from,const int to) {
        edge[from].push_back(to);
    }
    //xがflg_xならばyがflg_y
    inline void make_condition(int x, bool flg_x, int y, bool flg_y) {
        if (!flg_x) x = rev(x);
        if (!flg_y) y = rev(y);
        make_edge(x, y);
        make_edge(rev(y), rev(x));
    }
    //is_2sat=1のときに、2satを満たすかを返却する
    inline bool solve(void) {
        for (int i = 0; i < num; i++) if (order[i] == -1) dfs(i);
        for (int& id:label) id = max_id-1-id;
        if(!is_2sat) return true;
        for (int i = 0; i < num; ++i) if (label[i] == label[rev(i)]) return false;
        return true;
    }
    vector<vector<int>> topological_sort(void) {
        vector<vector<int>> ret(max_id);
        for(int i=0;i<num;++i) ret[label[i]].push_back(i);
        return ret;
    }
    int is_true(int i) {
        return label[i] > label[rev(i)];
    }
    void print(void) {
        for(auto id:label) cout << id << " ";
        cout << endl;
    }
};
#line 11 "test/graph/StronglyConnectedComponents-1.test.cpp"

int main(){
    int N,M; cin >> N >> M;
    vector<pair<int,int>> edge;
    vector<pair<int,int>> bedge;
    for(int i = 0; i < M; ++i) {
        int a,b; cin >> a >> b;
        a--,b--;
        int c; cin >> c;
        if(c==1){
            bedge.push_back({a,b});
        }
        else{
            edge.push_back({a,b});
        }
    }
    UnionFindTree uf(N);
    for(auto& e:bedge){
        int a = e.first,b = e.second;
        if(uf.connected(a,b)){
            cout << "Yes" << endl;
            return 0;
        }
        uf.merge(a,b);
    }
    StronglyConnectedComponents scc(N);
    for(auto& e:edge){
        int a = e.first,b = e.second;
        if(uf.connected(a,b)){
            cout << "Yes" << endl;
            return 0;
        }
        scc.make_edge(uf[a],uf[b]);
    }
    scc.solve();
    vector<int> cnt(N,0);
    for(int i = 0; i < N; ++i) cnt[scc[i]]++;
    for(int i = 0; i < N; ++i) if(cnt[i] > 1){
        cout << "Yes" << endl;
        return 0;
    }
    cout << "No" << endl; 
    return 0;
}
Back to top page