一直想找个时间整理一下自己常用的模板，方便自己查找。
图论还有很多算法，后期待完善。

最小生成树

kruskal

  • hdu1233
    也可以用贪心的方法，先定义一个数组，排序后并查集。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    #include<bits/stdc++.h>
    using namespace std;
    const int maxn = 20005;
    struct Node
    {
        int x,y,val;
        Node(){}
        Node(int a,int b,int c):x(a),y(b),val(c){}
        bool operator<(const Node& a)const 
        {
            return val > a.val;
        }
    };
    int B[maxn];
    int Find(int n)
    {
        return n == B[n] ? n:B[n]=Find(B[n]);
    }
    int main()
    {
        // ios::sync_with_stdio(false);
        // cin.tie(0);
        int N = 0;
        while(scanf("%d",&N)&&N){
            priority_queue<Node> Q;
            int a,b,c;
            int T = N*(N-1)/2;
            for(int i=1;i<=T;i++){
                B[i] = i;
            }
            for(int i=1;i<=T;i++){
                scanf("%d%d%d",&a,&b,&c);
                Q.push(Node(a,b,c));
            }
            int cnt = 0;
            int ans = 0;
            while(!Q.empty()&&cnt<N-1){
                Node t = Q.top();Q.pop();
                int t1 = Find(t.x);
                int t2 = Find(t.y);
                if(t1!=t2){
                    B[t2] = t1;
                    ans += t.val;
                    cnt++;
                }
            }
            printf("%d\n",ans);
        }
        return 0;
    }

prim算法

大体上和Dijksra算法相似

  • poj1258
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    #include<iostream>
    #include<cstring>
    #include<vector>
    #include<queue>
    using namespace std;
    const int maxn = 105;
    typedef pair<int,int> pii;
    int G[maxn][maxn];
    int dis[maxn];
    int N = 0;
    bool vis[maxn];

    int prim()
    {
        int ans = 0;
        memset(dis,0x7f,sizeof(dis));
        memset(vis,0,sizeof(vis));
        priority_queue<pii,vector<pii>,greater<pii> > Q;
        Q.push(pii(0,0));
        dis[0] = 0;
        while(!Q.empty()){
            pii t = Q.top();
            Q.pop();
            int u = t.first;
            int v = t.second;
            if(vis[v]) continue;
            vis[v] = 1;
            ans += u;
            for(int i=0;i<N;i++){
                if(i!=v){
                    int d = G[v][i];
                    if(dis[i] > d&&!vis[i]){ //唯一和dijkstra算法不一样的地方
                        dis[i] = d;          // 
                        Q.push(pii(dis[i],i));
                    }
                }
            }
        }
        return ans;
    }

    int main(int argc, char const *argv[])
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        while(cin >> N){
            for (int i = 0; i < N; i++)
            {
                for (int j = 0; j < N; j++)
                {
                    cin >> G[i][j];
                }
            }
            cout << prim() << endl;
        }
        return 0;
    }

最短路

dijkstra算法

  • poj2387
    用vecotr邻接表来表示图，适用于稀疏图
    优先队列版本的dijkstra算法。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    #include<iostream>
    #include<queue>
    #include<cstring>
    #include<vector>
    using namespace std;
    const int maxn = 10005;
    int T,N;
    vector<int> G[maxn];
    vector<int> D[maxn];
    int dis[maxn];
    const int inf = 1<<31;
    typedef pair<int,int> pii;

    int dijkstra()
    {
        memset(dis,10,sizeof(dis));
        bool vis[maxn];
        memset(vis,0,sizeof(vis));
        priority_queue<pii,vector<pii>,greater<pii> > Q;
        Q.push(pii(0,1));
        while(!Q.empty()){
            pii t = Q.top();
            Q.pop();
            int d = t.first;
            int a = t.second;
            if(vis[a])continue;
            vis[a] = 1;
            for(int i=0;i<G[a].size();i++){
                int j = G[a][i];
                int di = D[a][i];
                if(dis[j] > di + d){
                    dis[j] = di + d;
                    Q.push(pii(dis[j],j));
                }
            }
        }
        return dis[N];
    }

    int main()
    {
        cin >> T >> N;
        int a,b,c;
        for(int i=0;i<T;i++){
            cin >> a >> b >> c;
            G[a].push_back(b);
            G[b].push_back(a);
            D[a].push_back(c);
            D[b].push_back(c);
        }
        cout << dijkstra() << endl;

        return 0;
    }

bellman_ford算法

  • poj3259
    前M条边是双向边，后W条边是单向边，然后直接用bellman_ford算法判负环（自己用spfa判负环 结果WA了，不知道是测试数据卡spfa还是我spfa写错了）。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    #include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<queue>
    #include<vector>
    using namespace std;
    const int maxn = 1005;
    typedef pair<int,int> pii;
    int dis[maxn];
    int N,M,W;
    int k=0;

    struct Edge 
    {
        int to,from,cost;
    };
    Edge E[5000];

    bool bellman_Ford()
    {
        memset(dis,0,sizeof(dis));
        for(int i=1;i<=N;i++){
            for(int j=0;j<k;j++){
                Edge e = E[j];
                if(dis[e.to] > dis[e.from] + e.cost){
                    dis[e.to] = dis[e.from] + e.cost;
                    if(i==N) return false;
                }
            }
        }
        return true;
    }

    int main(int argc, char const *argv[])
    {
        int T = 0;
        cin >> T;
        while(T--){
            cin >> N >> M >> W;
            k = 0;
            int a,b,c;
            for(int i=0;i<M;i++){
                cin >> E[k].from >> E[k].to >> E[k].cost;
                E[k+1].from = E[k].to;
                E[k+1].to = E[k].from;
                E[k+1].cost =  E[k].cost;
                k += 2;
            }
            for(int i=0;i<W;i++){
                cin >> E[k].from >> E[k].to >> E[k].cost;
                E[k].cost = -E[k].cost;
                k++;
            }
            bool ok = bellman_Ford();
            if(ok){
                cout << "NO" <<  endl;
            }else{
                cout << "YES" << endl;
            }
        }
        return 0;
    }

SPFA算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<cstdio>
using namespace std;
struct node
{int x;
 int value;
 int next;
};
node e[60000];
int visited[1505],dis[1505],st[1505],queue[1000];
int main()
{
  int n,m,u,v,w,start,h,r,cur;
  freopen("c.in","r",stdin);
  freopen("c.out","w",stdout); 
  while(scanf("%d%d",&n,&m)!=EOF)
  {
    for(int i=1;i<=1500;i++)
      {visited[i]=0;
       dis[i]=-1;
       st[i]=-1;  //这个初始化给下边那个while循环带来影响
      }
 
   for(int i=1;i<=m;i++)
      {
       scanf("%d%d%d\n",&u,&v,&w);     
       e[i].x=v;            //记录后继节点    相当于链表中的创建一个节点，并使得数据域先记录
       e[i].value=w;
       e[i].next=st[u];     //记录顶点节点的某一个边表节点的下标，相当于在链表中吧该边表节点的next指针先指向他的后继边表节点
       st[u]=i;                //把该顶点的指针指向边表节点，相当于链表中的插入中，头结点的指针改变
      }
    start=1;
    visited[start]=1;
    dis[start]=0;
    h=0;
    r=1;
    queue[r]=start;
    while(h!=r)
     {

      h=(h+1)%1000;
      cur=queue[h];
      int tmp=st[cur];
      visited[cur]=0;
    

     while(tmp!=-1)
        {
            if (dis[e[tmp].x]<dis[cur]+e[tmp].value)            //改成大于号才对
            {
                   dis[e[tmp].x]=dis[cur]+e[tmp].value;
                    if(visited[e[tmp].x]==0)
                      {

                           visited[e[tmp].x]=1;
                           r=(r+1)%1000;
                            queue[r]=e[tmp].x;
                       }
            }
         tmp=e[tmp].next;      
        }
     } 
    printf("%d\n",dis[n]);
  }
  return 0;   
}

Flody算法

1
2
3
4
5
6
7
8
9
10
11
for (int i = 0; i < n; i++) {   //  初始化为0  
    for (int j = 0; j < n; j++)  
        scanf("%lf", &dis[i][j]);  
}  
for (int k = 0; k < n; k++) {  
    for (int i = 0; i < n; i++) {  
        for (int j = 0; j < n; j++) {  
            dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);  
        }  
    }
}

网络流

增广路算法

  • 计蒜课排涝
    模板题
    EdmondsKarp也可用于二分图的最大基数匹配，在二分图的左边后右边都添加一个结点，然后分别和二分图两边的结点相连即可。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    #include <bits/stdc++.h>

    using namespace std;
    const int maxn = 205;
    const int INF = 1<<30;
    struct Edge
    {
        int from,to,cap,flow;
        Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f){}
    };

    struct Dinic        //更快
    {
        int n,m,s,t;
        vector<Edge> edges;
        vector<int> G[maxn];
        bool vis[maxn];
        int d[maxn];
        int cur[maxn];

        void init(int n){
            for(int i=0;i<n;i++) G[i].clear();
            edges.clear();
        }

        void AddEdge(int from,int to,int cap){
            edges.push_back(Edge(from,to,cap,0));
            edges.push_back(Edge(to,from,0,0));
            m = edges.size();
            G[from].push_back(m-2);
            G[to].push_back(m-1);
        }

        bool BFS()
        {
            memset(vis,0,sizeof(vis));
            queue<int> Q;
            Q.push(s);
            d[s] = 0;
            vis[s] = 1;
            while(!Q.empty()){
                int x = Q.front();
                Q.pop();
                for(int i=0;i<G[x].size();i++){
                    Edge& e = edges[G[x][i]];
                    if(!vis[e.to]&&e.cap > e.flow){
                        vis[e.to] = 1;
                        d[e.to] = d[x]+1;
                        Q.push(e.to);
                    }
                }
            }
            return vis[t];
        }

        int DFS(int x,int a){
            if(x==t || a==0)return a;
            int flow = 0,f;
            for(int &i=cur[x];i<G[x].size();i++){
                Edge& e = edges[G[x][i]];
                if(d[x]+1==d[e.to] && (f=DFS(e.to,min(a,e.cap-e.flow)))>0){
                    e.flow += f;
                    edges[G[x][i]^1].flow -= f;
                    flow += f;
                    a -= f;
                    if(a==0)break;
                }
            }
            return flow;
        }

        int Maxflow(int s,int t){
            this->s = s,this->t = t;
            int flow = 0;
            while(BFS()){
                memset(cur,0,sizeof(cur));
                flow += DFS(s,INF);
            }
            return flow;
        }
        
    };

    struct EdmondsKarp
    {
        int n,m;
        vector<Edge> edges;
        vector<int> G[maxn];
        int a[maxn];
        int p[maxn];

        void init(int n){
            for(int i=0;i<n;i++) G[i].clear();
            edges.clear();
        }

        void AddEdge(int from,int to,int cap){
            edges.push_back(Edge(from,to,cap,0));
            edges.push_back(Edge(to,from,0,0));
            m = edges.size();
            G[from].push_back(m-2);
            G[to].push_back(m-1);
        }

        int Maxflow(int s,int t){
            int flow = 0;
            while(1){
                memset(a,0,sizeof(a));
                queue<int> Q;
                Q.push(s);
                a[s] = INF;
                while(!Q.empty()){
                    int x = Q.front();Q.pop();
                    for(int i=0;i<G[x].size();i++){
                        Edge& e = edges[G[x][i]];
                        if(!a[e.to]&&e.cap>e.flow){
                            p[e.to] = G[x][i];
                            a[e.to] = min(a[x],e.cap-e.flow);
                            Q.push(e.to);
                        }
                    }
                    
                    if(a[t]) break;
                }
                if(!a[t])break;
                for(int u=t;u!=s;u=edges[p[u]].from){
                    edges[p[u]].flow += a[t];
                    edges[p[u]^1].flow -= a[t];
                }
                flow += a[t];
            }
            return flow;
        }
    };

    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        int n,m;
        cin >> n >> m;
        EdmondsKarp s;
        int a,b,c;
        for(int i=0;i<n;i++){
            cin >> a >> b >>c;
            s.AddEdge(a,b,c);
        }
        cout << s.Maxflow(1,m) <<endl;
    }

最小费用最大流

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 1<<30;

const int maxn = 10005;
struct Edge{
    int from ,to,cap,flow,cost;
    Edge(int u,int v,int c,int f,int w):from(u),to(v),cap(c),flow(f),cost(w){}
};

struct MCMF{
    int n,m;
    vector<Edge> edges;
    vector<int> G[maxn];
    int inq[maxn];  //是否在队列中
    int d[maxn];    //Bellman-Ford
    int p[maxn];    //上一条弧
    int a[maxn];    //可改进量

    void init(int n)
    {
        this-> n = n;
        for(int i=0;i<n;i++){
            G[i].clear();
        }
        edges.clear();
    }

    void AddEdge(int from,int to,int cap,int cost)
    {
        edges.push_back(Edge(from,to,cap,0,cost));
        edges.push_back(Edge(to,from,0,0,-cost));
        m = edges.size();
        G[from].push_back(m-2);
        G[to].push_back(m-1);
    }
    
    bool BellmanFord(int s,int t,int& flow,ll& cost)
    {
        for(int i=0;i<n;i++) d[i] = INF;
        memset(inq,0,sizeof(inq));
        d[s] = 0;inq[s]  = 1;p[s] = 0;a[s] = INF;

        queue<int> Q;
        Q.push(s);
        while(!Q.empty()){
            int u = Q.front();Q.pop();
            inq[u] = 0;
            for(int i=0;i<G[u].size();i++){
                Edge& e = edges[G[u][i]];
                if(e.cap > e.flow && d[e.to] > d[u] + e.cost){
                    d[e.to] = d[u] + e.cost;
                    p[e.to] = G[u][i];
                    a[e.to] = min(a[u],e.cap - e.flow);
                    if(!inq[e.to]){
                        Q.push(e.to);
                        inq[e.to] = 1;
                    }
                }
            }
            if(d[t] == INF) return false;
            flow += a[t];
            cost += (ll)d[t] + a[t];
            edges[p[u]].flow += a[t];
            edges[p[u]^1].flow -= a[t];
        }
        return true;
    }

    int MincostMaxflow(int s,int t,ll& cost){
        int flow = 0;cost = 0;
        while(BellmanFord(s,t,flow,cost));
        return flow;
    }
};

二分图

二分图判断（交叉染色）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
static int speed_up = []() {
	 ios::sync_with_stdio(false);
	 cin.tie(nullptr);
	 return 0;
 }();
const int MAX_N = 2005;
int V;
vector<int> G[MAX_N];

int color[MAX_N];
 
bool dfs(int v, int c)
{
    color[v] = c; 
    for(int i = 0; i < G[v].size(); i++)
    {
        int j = G[v][i];
        if(color[j] == c)
            return false;
        if(color[j] == 0 && !dfs(j, -c))
            return false;
    }
    return true;
}
 
bool solve()
{
    for(int i = 1; i <= V; i++)
    {
        if(color[i] == 0)
        {
            if(!dfs(i,1))
            {
                
                return false;
            }
        }
    }
    return true;
}


class Solution {
public:
    bool possibleBipartition(int N, vector<vector<int>>& dislikes) {
        V = N;
        for(int i=0;i<=N;i++){
            G[i].clear();
        }
       memset(color,0,sizeof(color));
        for(int i=0;i<dislikes.size();i++){
            int u = dislikes[i][0];
            int v = dislikes[i][1];
            
            G[u].push_back(v);
            G[v].push_back(u);
        }
        return solve();
    }
};

无向图割边割点和双连通分量

  • uva315
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    #include <bits/stdc++.h>
    using namespace std;
    #define mclear(x) memset((x), 0, sizeof((x)))
    typedef pair<int, int> pii;
    const int MAX = 5100;
    int n, m, deep;
    vector<int> path[MAX];
    int vis[MAX], low[MAX];
    vector<int> cutpoint; //割点
    vector<pii> bridge;   //割边,桥
    int nbcc;             //双连通分量数
    stack<pii> order;
    vector<int> bcc[MAX]; //双连通分量

    void dfs(int pos, int father)
    {
        int i, j, total = 0;
        bool cut = false;
        int reback = 0; //处理平行边
        vis[pos] = low[pos] = deep++;
        int ls = path[pos].size();
        for (j = 0; j < ls; j++)
        {
            i = path[pos][j];
            if (i == father)
                reback++;
            if (vis[i] == 0)
            {
                pii e(pos, i);
                order.push(e);
                dfs(i, pos);
                if (low[i] >= vis[pos])
                {
                    nbcc++;
                    bcc[nbcc].clear();
                    pii r;
                    do
                    {
                        r = order.top();
                        order.pop();
                        bcc[nbcc].push_back(r.second);
                    } while (e != r);
                    bcc[nbcc].push_back(r.first);
                }
                total++;
                low[pos] = min(low[i], low[pos]);
                if ((vis[pos] == 1 && total > 1) ||
                    (vis[pos] != 1 && low[i] >= vis[pos]))
                    cut = true;
                if (low[i] > vis[pos])
                    bridge.push_back(e);
            }
            else if (i != father)
            {
                low[pos] = min(vis[i], low[pos]);
            }
        }
        if (reback > 1)
            low[pos] = min(low[pos], vis[father]);
        if (cut)
            cutpoint.push_back(pos);
    }
    void find_cut()
    {
        int i;
        mclear(vis);
        mclear(low);
        cutpoint.clear();
        bridge.clear();
        nbcc = 0;
        while (!order.empty())
            order.pop();
        for (i = 1; i <= n; i++)
        {
            if (vis[i] == 0)
            {
                deep = 1;
                dfs(i, -1);
            }
        }
    }

    int main()
    {
        while (~scanf("%d", &n) && n)
        {
            int a = 0;
            char c;
            vector<int> vet;
            for (int i = 0; i <= n; i++)
            {
                path[i].clear();
            }
            int u = 0;
            while (scanf("%d", &u) && u)
            {
                while (scanf("%c", &c)&&c==' ')
                {
                    scanf("%d",&a);
                    path[u].push_back(a);
                    path[a].push_back(u);
                }
            }
            find_cut();
            cout << cutpoint.size() << endl;
        }

        return 0;
    }

强连通分量

SCC的Tarjan算法

  • poj1236
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    #include<iostream>
    #include<cstring>
    #include<queue>
    #include<cstdio>
    #include<stack>
    #include<algorithm>
    #include<vector>

    using namespace std;
    const int maxn = 105;
    vector<int> G[maxn];
    bool M[maxn][maxn];
    int pre[maxn],lowlink[maxn],sccno[maxn],dfs_clock,scc_cnt;
    int out[maxn],in[maxn];
    stack<int> S;

    int dfs(int u)
    {
        pre[u] = lowlink[u] = ++dfs_clock;
        S.push(u);
        for(int i=0;i<G[u].size();i++){
            int v = G[u][i];
            if(!pre[v]){
                dfs(v);
                lowlink[u] = min(lowlink[u],lowlink[v]);
            }else if(!sccno[v]){
                lowlink[u] = min(lowlink[u],pre[v]);
            }
        }
        if(lowlink[u] == pre[u]){
            scc_cnt++;
            while(1){
                int x = S.top();S.pop();
                sccno[x] = scc_cnt;
                if(x==u)break;
            }
        }
    }

    void find_scc(int n)
    {
        dfs_clock = scc_cnt = 0;
        memset(sccno,0,sizeof(sccno));
        memset(pre,0,sizeof(pre));
        memset(out,0,sizeof(out));
        memset(in,0,sizeof(in));
        for(int i=1;i<=n;i++){
            if(!pre[i])dfs(i);
        }
        if(scc_cnt==1){
            cout << "1\n0\n";
            return;
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(M[i][j]&&sccno[i]!=sccno[j]){
                    out[sccno[i]]++;
                    in[sccno[j]]++;
                }
            }
        }
        int ans1 = 0,ans2 = 0;
        for(int i=1;i<=scc_cnt;i++){
            if(in[i]==0)ans1++;
            if(out[i]==0)ans2++;
        }
        cout << ans1 << endl << max(ans1,ans2) << endl;
    }


    int main()
    {
        int N  = 0;
        cin >> N;
        int a = 0;
        for(int i=1;i<=N;i++){
            while(cin >> a&&a){
                G[i].push_back(a);
                M[i][a] = 1;
            }
        }
        
        find_scc(N);

        return 0;
    }