Select Git revision
URI1128.cpp
-
Bruno Freitas Tissei authored
Signed-off-by:
Bruno Freitas Tissei <bft15@inf.ufpr.br>
Bruno Freitas Tissei authoredSigned-off-by:
Bruno Freitas Tissei <bft15@inf.ufpr.br>
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;
}