cfgym100519G

201707

• 题目信息
  
  • 每个点的出度最多为1。
  • 图不保证联通。
  • 求图中最长的链的节点个数。如果有结点没有父亲，不计入该节点。
• 比赛时的错误
  
  • 每次从入度0的点出发，直到无路可走。
  • 这样的算法会导致多次走重复路径。
• 仔细想想，如果一个点走到一个环上，它接下来能走的路就是这个环的大小。于是预处理出所有环即可。
• 注：2e5个长度为20的string丢到map不会超时。

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define sz(x) (int)x.size()
#define de(x) cout<< #x<<" = "<<x<<endl
typedef long long ll;
typedef pair<int, int> pii;
//------
const int N=200005;
bool vis[N],o[N];
int n,tim,p;
int pre[N],deg[N],f[N],sta[N];
map<string,int> id;
void dfs(int u) {
    if(vis[u]) return ;
    vis[u]=1;
    sta[++p]=u;
    dfs(pre[u]);
}
int calc(int u) {
    if(~f[u]) return f[u];
    if(pre[u]==-1) return f[u]=0;
    return f[u]=1+calc(pre[u]);
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    memset(pre,-1,sizeof(pre));
    memset(f,-1,sizeof(f));
    ///read
    rep(i,0,n) {
        int u,v;
        string a,b,c;
        cin>>a>>b>>c>>c>>c;
        v=id[a+b];
        if(v==0) {
            id[a+b]=++tim;
            v=tim;
        }
        u=id[a+c];
        if(u==0) {
            id[a+c]=++tim;
            u=tim;
        }
        pre[v]=u;
        ++deg[u];
    }
    ///solve
    vector<int> q;
    int ans=0;
    rep(i,1,tim+1) {
        if(deg[i]==0) {
            o[i]=1;
            q.pb(i);vis[i]=1;
        }
    }
    rep(i,0,sz(q)) {
        int u=q[i],v=pre[u];
        if(vis[v]) continue;
        --deg[v];
        if(deg[v]==0) {
            q.pb(v);
            vis[v]=1;
        }
    }
    rep(i,1,tim+1) {
        if(!vis[i]) {
            p=0;
            dfs(i);
            rep(j,1,p+1) f[sta[j]]=p;
            ans=max(ans,p);
        }
    }
    rep(i,1,tim+1) {
        if(o[i]) ans=max(calc(i),ans);
    }
    ///print    
    cout<<ans<<endl;
    return 0;
}