Skip to content
Snippets Groups Projects
Select Git revision
  • master default protected
1 result

URI1128.cpp

Blame
  • URI1128.cpp 1.54 KiB
    #include <bits/stdc++.h>
    
    #define MAX 2010
    #define EPS 1e-6
    #define MOD 1000000007
    #define inf 0x3f3f3f3f
    #define llinf 0x3f3f3f3f3f3f3f3f
    
    #define fi first
    #define se second
    #define pb push_back
    #define ende '\n'
    
    #define all(x) (x).begin(), (x).end()
    #define rall(x) (x).rbegin(), (x).rend()
    #define mset(x, y) memset(&x, (y), sizeof(x))
    
    using namespace std; 
    
    typedef long long ll;
    typedef pair<int,int> ii;
    
    stack<int> S;
    vector<int> graph[MAX];
    
    int ncomp, ind;
    int visited[MAX];
    
    int id[MAX];
    
    int low[MAX];
    
    vector<int> scc[MAX];
    
    void dfs(int x) {
      id[x] = low[x] = ind++;
      visited[x] = 1;
    
      S.push(x);
    
      for (auto i : graph[x])
        if (id[i] == -1) {
          dfs(i);
    
          low[x] = min(low[x], low[i]);
    
        } else if (visited[i])
          low[x] = min(low[x], id[i]);
    
      if (low[x] == id[x]) {
        int w;
    
        do {
          w = S.top(); S.pop();
          visited[w] = 0;
          scc[ncomp].pb(w);
        } while (w != x);
    
        ncomp++;
      }
    }
    
    int tarjan(int n) {
      mset(id, -1);
      ncomp = ind = 0;
    
      for (int i = 0; i < n; ++i)
        scc[i].clear();
    
      for (int i = 0; i < n; ++i)
        if (id[i] == -1)
          dfs(i);
    
      return ncomp;
    }
    
    
    int main() {
      ios::sync_with_stdio(0);
      cin.tie(0);
    
      int n, m;
      while (cin >> n >> m && (n || m)) {
        for (int i = 0; i < n; ++i)
          graph[i].clear();
    
        for (int i = 0; i < m; ++i) {
          int v, w, p; cin >> v >> w >> p;
          v--, w--;
          if (p == 1)
            graph[v].pb(w);
          else {
            graph[v].pb(w);
            graph[w].pb(v);
          }
        }
    
        int ans = tarjan(n);
        cout << (ans == 1) << ende;
      }
    
      return 0;
    }