首页 > 代码库 > zoj-3795-Grouping-tarjan缩点求最长路
zoj-3795-Grouping-tarjan缩点求最长路
用tarjan进行缩点。
然后用dfs求最长路。水体。。。
#include<stdio.h> #include<string.h> #include<algorithm> #include<iostream> #include<vector> #include<map> #include<stack> using namespace std; #define maxn 110000 vector<int>old[maxn]; vector<int>vec[maxn]; int dnf[maxn],low[maxn],instack[maxn]; int times,nums; stack<int>st; int pan[maxn]; int ru[maxn]; int vis[maxn]; int ans; int res[maxn]; int val[maxn]; void init(int n) { for(int i=0;i<=n+1;i++) { dnf[i]=low[i]=instack[i] =pan[i]=ru[i]=vis[i]=res[i]=val[i]=0; vec[i].clear();old[i].clear(); } while(!st.empty())st.pop(); times=nums=1; } void tarjan(int x) { dnf[x]=low[x]=times++; instack[x]=1; st.push(x); for(int i=0;i<old[x].size();i++) { int y=old[x][i]; if(!dnf[y]) { tarjan(y); low[x]=min(low[x],low[y]); } else if(instack[y]) { low[x]=min(low[x],dnf[y]); } } if(low[x]==dnf[x]) { int y=-1; while(x!=y) { y=st.top(); st.pop(); instack[y]=0; pan[y]=nums; val[nums]++; } nums++; } } void dfs(int x) { if(res[x])return; res[x]=val[x]; for(int i=0;i<vec[x].size();i++) { int y=vec[x][i]; dfs(y); res[x]=max(res[x],res[y]+val[x]); } } int main() { int n,m,x,y; while(~scanf("%d%d",&n,&m)) { init(n); while(m--) { scanf("%d%d",&x,&y); old[x].push_back(y); } for(int i=1;i<=n;i++) if(!dnf[i])tarjan(i); for(int i=1;i<=n;i++) { for(int j=0;j<old[i].size();j++) { x=pan[i]; y=pan[old[i][j]]; if(x==y)continue; vec[x].push_back(y); ru[y]++; } } ans=-1; for(int i=1;i<nums;i++) { if(!ru[i]) { dfs(i); ans=max(ans,res[i]); } } cout<<ans<<endl; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。