fork(1) download

copy

#include <vector>
#include <algorithm>
#include <iostream>
#include <cstdio>
 
using namespace std;
 
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  FOR(i,0,n)
 
struct edge{ 
    int to, id;
    edge(int to, int id) : to(to), id(id){}
    edge(){}
};
 
struct unionfind {
    vector<int> par, rank;
 
    void init(int n) {
	par.resize(n);
	rank.resize(n);
 
	for(int i = 0; i < n; i++) {
	    par[i] = i;
	    rank[i] = 0;
	}
    }
 
    int find(int x) {
	if(par[x] == x) return x;
	else return par[x] = find(par[x]);
    }
 
    void unite(int x, int y) {
	x = find(x);
	y = find(y);
	if(x == y) return ;
 
	if(rank[x] < rank[y]) par[x] = y;
	else{
	    par[y] = x;
	    if(rank[x] == rank[y]) ++rank[x];
	}
    }
 
    bool same(int x, int y) { return (find(x) == find(y)); }
} uf;
 
int n;
int now;
vector<edge> g[5010];
vector<edge> in[5010];
bool vis[5010];
vector<int> v[5010];
vector<int> gg[100010];
int dp[100010];
vector<int> vs;
vector<int> em;
 
void predfs(int v){
    vis[v] = true;
    rep(i, g[v].size()){
	in[g[v][i].to].pb(edge(v, g[v][i].id));
	if(!vis[g[v][i].to]) predfs(g[v][i].to);
    }
}
 
void dfs(int v){
    vis[v] = true;
    rep(i, gg[v].size()){
	if(!vis[gg[v][i]]) dfs(gg[v][i]);
    }
    vs.pb(v);
}
 
int main(){
    scanf("%d", &n);
 
    rep(i, n - 1){
	int k;
	scanf("%d", &k);
	g[i].resize(k);
	rep(j, k){
	    int x;
	    scanf("%d", &x);
	    --x;
	    g[i][j] = edge(x, now++);
	}
    }
 
    predfs(0);
    rep(i, n) reverse(in[i].begin(), in[i].end());
    uf.init(now * 2);
 
    rep(i, n){
	rep(j, in[i].size()){
	    v[i].pb(in[i][j].id * 2 + 1);
	    v[i].pb(in[i][j].id * 2);
	}
 
	rep(j, g[i].size()){
	    v[i].pb(g[i][j].id * 2);
	    v[i].pb(g[i][j].id * 2 + 1);
	}
 
	rep(j, (int)v[i].size() / 2 - 1){
	    uf.unite(v[i][j * 2 + 1], v[i][j * 2 + 2]);
	}
	uf.unite(v[i][0], v[i].back());
    }
 
    rep(i, now * 2) em.pb(uf.find(i));
    sort(em.begin(), em.end());
    em.erase(unique(em.begin(), em.end()), em.end());
 
 
    rep(i, n){
	rep(j, g[i].size()){
	    int u = uf.find(g[i][j].id * 2);
	    u = lower_bound(em.begin(), em.end(), u) - em.begin();
	    int v = uf.find(g[i][j].id * 2 + 1);
	    v = lower_bound(em.begin(), em.end(), v) - em.begin();
	    if(v != 0) gg[u].pb(v);
	}
    }
 
    rep(i, em.size()){
	sort(gg[i].begin(), gg[i].end());
	gg[i].erase(unique(gg[i].begin(), gg[i].end()), gg[i].end());
    }
 
    memset(vis, 0, sizeof(vis));
    rep(i, em.size()){
	if(vis[i] || !gg[i].size()) continue;
	dfs(i);
    }
    reverse(vs.begin(), vs.end());
 
    dp[0] = 1;
    rep(i, vs.size()) rep(j, gg[vs[i]].size()) dp[gg[vs[i]][j]] = max(dp[gg[vs[i]][j]], dp[vs[i]] + 1);
 
    printf("%d\n", *max_element(dp, dp + (int)em.size()));
    return 0;
}

prog.cpp: In function ‘void predfs(int)’:
prog.cpp:12:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i,a,b) for(int i=(a);i<(b);++i)
                                      ^
prog.cpp:13:19: note: in expansion of macro ‘FOR’
 #define rep(i,n)  FOR(i,0,n)
                   ^
prog.cpp:67:5: note: in expansion of macro ‘rep’
     rep(i, g[v].size()){
     ^
prog.cpp: In function ‘void dfs(int)’:
prog.cpp:12:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i,a,b) for(int i=(a);i<(b);++i)
                                      ^
prog.cpp:13:19: note: in expansion of macro ‘FOR’
 #define rep(i,n)  FOR(i,0,n)
                   ^
prog.cpp:75:5: note: in expansion of macro ‘rep’
     rep(i, gg[v].size()){
     ^
prog.cpp: In function ‘int main()’:
prog.cpp:12:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i,a,b) for(int i=(a);i<(b);++i)
                                      ^
prog.cpp:13:19: note: in expansion of macro ‘FOR’
 #define rep(i,n)  FOR(i,0,n)
                   ^
prog.cpp:101:2: note: in expansion of macro ‘rep’
  rep(j, in[i].size()){
  ^
prog.cpp:12:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i,a,b) for(int i=(a);i<(b);++i)
                                      ^
prog.cpp:13:19: note: in expansion of macro ‘FOR’
 #define rep(i,n)  FOR(i,0,n)
                   ^
prog.cpp:106:2: note: in expansion of macro ‘rep’
  rep(j, g[i].size()){
  ^
prog.cpp:12:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i,a,b) for(int i=(a);i<(b);++i)
                                      ^
prog.cpp:13:19: note: in expansion of macro ‘FOR’
 #define rep(i,n)  FOR(i,0,n)
                   ^
prog.cpp:123:2: note: in expansion of macro ‘rep’
  rep(j, g[i].size()){
  ^
prog.cpp:12:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i,a,b) for(int i=(a);i<(b);++i)
                                      ^
prog.cpp:13:19: note: in expansion of macro ‘FOR’
 #define rep(i,n)  FOR(i,0,n)
                   ^
prog.cpp:132:5: note: in expansion of macro ‘rep’
     rep(i, em.size()){
     ^
prog.cpp:137:31: error: ‘memset’ was not declared in this scope
     memset(vis, 0, sizeof(vis));
                               ^
prog.cpp:12:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i,a,b) for(int i=(a);i<(b);++i)
                                      ^
prog.cpp:13:19: note: in expansion of macro ‘FOR’
 #define rep(i,n)  FOR(i,0,n)
                   ^
prog.cpp:138:5: note: in expansion of macro ‘rep’
     rep(i, em.size()){
     ^
prog.cpp:12:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i,a,b) for(int i=(a);i<(b);++i)
                                      ^
prog.cpp:13:19: note: in expansion of macro ‘FOR’
 #define rep(i,n)  FOR(i,0,n)
                   ^
prog.cpp:145:5: note: in expansion of macro ‘rep’
     rep(i, vs.size()) rep(j, gg[vs[i]].size()) dp[gg[vs[i]][j]] = max(dp[gg[vs[i]][j]], dp[vs[i]] + 1);
     ^
prog.cpp:12:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i,a,b) for(int i=(a);i<(b);++i)
                                      ^
prog.cpp:13:19: note: in expansion of macro ‘FOR’
 #define rep(i,n)  FOR(i,0,n)
                   ^
prog.cpp:145:23: note: in expansion of macro ‘rep’
     rep(i, vs.size()) rep(j, gg[vs[i]].size()) dp[gg[vs[i]][j]] = max(dp[gg[vs[i]][j]], dp[vs[i]] + 1);
                       ^

Standard output is empty