忙碌的小L （月赛题解，targin）

解题思路:

    23333,4月月赛题目，这道题目是入门题是真的坑，哪有入门这么难的ε=ε=ε=(~￣▽￣)~，抢个首题解，顺手感谢小闷骚大佬的思路

    这道题目直接用并查集做，方正我直接一套模板下去过了90%的数据，实际上是不行的，因为这是一个既有单向也有双向连接的边，最后答案能过多少取决于数据的水分。

    1、这里我们用的是强连通分量的做法，把有环的组成一团，比如2教3，3教4，4教2，这样的为一个团（学过强连通的应该就懂了）。 这时候只要教会这个团任何一个人，该团的所有人都会被教会。

    2、经过targin算法我们已经把所有的点分为很多大大小小的团，这时候我们就可以知道所有团之间已经没有了回路，只有单向边，或者独立团，这时候要教的次数就等于 独立团的团数 + 没有入度的团数，枚举判断就行了。

    答案 = 独立团的团数 + 没有入度的团数

注意事项:

    没有什么特别坑的数据，写判断的时候小心一点就行

参考代码:

#include <bits/stdc++.h>

using namespace std;

const int mod = 1e9+7;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int,int> pii;

const int INF = 0x3f3f3f3f;

const int maxn = 220;   //点数

const int maxm = 40010; //边数

struct Edge{

    int to,nxt;

}edge[maxm];

int head[maxn],tot; //点头和边数

int Low[maxn],Dfn[maxn],Stack[maxn],Belong[maxn];

int Index,top;

int scc;

bool Instack[maxn];

void addedge(int u, int v) {

    edge[tot].to = v;

    edge[tot].nxt = head[u];

    head[u] = tot++;

}

void init(){

    tot = 0;

    memset(head,-1,sizeof head);

}

void Tarjin(int u) {

    int v;

    Low[u] = Dfn[u] = ++Index;

    Stack[top++] = u;

    Instack[u] = true;

    for(int i = head[u]; i != -1; i = edge[i].nxt) {

        v = edge[i].to;

        if(!Dfn[v]) {

            Tarjin(v);

            if(Low[u] > Low[v]) Low[u] = Low[v];

        }

        else if(Instack[v] && Low[u] > Dfn[v]) {

            Low[u] = Dfn[v];

        }

    }

    if(Low[u] == Dfn[u]) {

        scc++;

        do{

            v = Stack[--top];

            Instack[v] = false;

            Belong[v] = scc;

        } while(v != u);

    }

}

void solve(int n) {

    memset(Dfn,0,sizeof Dfn);

    memset(Instack, false, sizeof Instack);

    Index = scc = top = 0;

    for(int i = 1; i <= n; i++) {

        if(!Dfn[i])

            Tarjin(i);

    }

}

//以上全是kuangbin模板，可以套其他模板

vector<int> bj[maxn];   //每个点保存本人能被谁教

int tmp,n;

int main() {

    init();

    scanf("%d",&n);

    for(int i = 1; i <= n; i++) {

        while(scanf("%d",&tmp) == 1 && tmp) {

            bj[tmp].push_back(i);

            addedge(i,tmp);

        }

    }

    solve(n);

    int ans = 0;

    int is[maxn] = {0};   //判断该团有没有人教

    for(int i = 1; i <= n; i++) {

        if(is[Belong[i]] == 0) {

            int len = bj[i].size();

            for(int j = 0; j < len; j++) {

                int v = bj[i][j];

                if(Belong[v] != Belong[i]) {

                    is[Belong[i]] = 1;

                    break;

                }

            }

        }

    }

    for(int i = 1; i <= scc; i++) {

        if(is[i] == 0) ans++;

    }

    printf("%d\n",ans);

    return 0;

}