Create a gist now

Instantly share code, notes, and snippets.

#include<bits/stdc++.h>
using namespace std;
#define MAX_N 100005
#define MAX_M 100005
int n,m,ans;
int x[MAX_M],y[MAX_M],w[MAX_M];
vector<int> G[MAX_N];
vector<int> g[MAX_N];
vector<int> group[MAX_N];
int id[MAX_N];
bool visited[MAX_N];
vector<int> vd;
int dp[MAX_N];
int d[MAX_N];
bool dfs(int pos,int prev,int root){
id[pos]=root;
visited[pos]=true;
group[root].push_back(pos);
for(int i=0;i<(int)G[pos].size();i++){
int to=G[pos][i];
if(to==prev)continue;
if(i&&to==G[pos][i-1])return true;
if(visited[to])return true;
if(dfs(to,pos,root))return true;
}
return false;
}
bool check(){
memset(visited,false,sizeof(visited));
for(int i=0;i<n;i++)
if(!visited[i]&&dfs(i,-1,i))return true;
vector<int> deg(n);
for(int pos=0;pos<n;pos++)
for(int to:g[pos])
deg[ id[to] ]++;
queue<int> Q;
for(int i=0;i<n;i++)
if(deg[i]==0&&id[i]==i)
Q.push(i);
while(!Q.empty()){
int root=Q.front();Q.pop();
vd.push_back(root);
for(int pos:group[root]){
for(int to:g[pos]){
deg[ id[to] ]--;
if(deg[ id[to] ]==0)Q.push(id[to]);
}
}
}
for(int i=0;i<n;i++)
if(deg[i]>0)return true;
return false;
}
int solve(int S){
for(int pos:group[id[S]])d[pos]=-1;
queue<int> Q;
Q.push(S);
d[S]=0;
while(!Q.empty()){
int pos=Q.front();Q.pop();
for(int to:G[pos]){
if(d[to]!=-1)continue;
d[to]=d[pos]+1;
Q.push(to);
}
}
int res=S;
for(int pos:group[id[S]]){
if(d[pos]+dp[pos]>d[res]+dp[res])res=pos;
ans=max(ans,d[pos]+dp[S]);
for(int to:g[pos])dp[to]=max(dp[to],d[pos]+dp[S]+1);
}
return res;
}
int main(){
scanf("%d %d",&n,&m);
for(int i=0;i<m;i++){
scanf("%d %d %d",&x[i],&y[i],&w[i]);
x[i]--,y[i]--;
if(w[i]==1){
g[x[i]].push_back(y[i]);
}
if(w[i]==2){
G[x[i]].push_back(y[i]);
G[y[i]].push_back(x[i]);
}
}
if(check()){
printf("Infinite\n");
return 0;
}
for(int root : vd )
if(root==id[root])
solve(solve(solve(root)));
printf("%d\n",ans);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment