<h1>概念</h1>

我们先来明确一些概念。

<h2>子图</h2>

图G=(V，E)，G’=(V’，E’)中，若V’ ∈ V，E’ ∈ E，并且E’中的边所关联的顶点都在V’中，则称图G’是图G的子图

<h2>强连通性</h2>

对有向图G=(V,E)而言，若对于G中任意两个顶点Vi和Vj（Vi≠Vj ），都有一条从Vi到Vj的（有向路径），同时还有一条从Vj到Vi的(有向)路径，则称有向图G是强连通的

<h2>强连通分量（SCC）</h2>

有向图强连通的 极大 子图

<h1>Tarjan算法实现</h1>

Tarjan算法用于求有向图强连通分量，其过程主要如下：
做一遍DFS，用dfn[i]表示编号为i的节点在DFS过程中的访问序号(也可以叫做开始时间）用low[i]表示i节点DFS过程中i的下方节点所能到达的开始时间最早的节点的开始时间。初始时dfn[i]=low[i]
在DFS过程中会形成一搜索树。在搜索树上越先遍历到的节点，显然dfn的值就越小。
DFS过程中，碰到哪个节点，就将哪个节点入栈。栈中节点只有在其所属的强连通分量已经全部求出时，才会出栈。
如果发现某节点u有边连到搜索树中栈里的节点v，则更新u的low 值为dfn[v](更新为low[v]也可以）。
如果一个节点u已经DFS访问结束，而且此时其low值等于dfn值，则说明u可达的所有节点，都不能到达任何在u之前被DFS访问的节点，那么该节点u就是一个强连通分量在DFS搜索树中的根。
此时将栈中所有节点弹出，包括u,就找到了一个强连通分量

<h1>作用</h1>

它能用来做什么呢？
它能将一个复杂的图缩点：就是将每一个强连通分量都缩成一个点。
缩点前：

缩点后：

<h1>例题</h1>

CodeVS 2822

<h2>题目描述</h2>

每个人都拥有一个梦，即使彼此不相同，能够与你分享，无论失败成功都会感动。爱因为在心中，平凡而不平庸，世界就像迷宫，却又让我们此刻相逢Our Home。

在爱的国度里有 N 个人，在他们的心中都有着一个爱的名单，上面记载着他所爱的人（不会出现自爱的情况）。爱是具有传递性的，即如果 A 爱 B，B 爱 C，则 A 也爱 C。

如果有这样一部分人，他们彼此都相爱，则他们就超越了一切的限制，用集体的爱化身成为一个爱心天使。现在，我们想知道在这个爱的国度里会出现多少爱心天使。而且，如果某个爱心天使被其他所有人或爱心天使所爱则请输出这个爱心天使是由哪些人构成的，否则输出 -1。

<h2>题解</h2>

第一问：求出图中有多少不是单点的强连通分量就是答案。
第二问：把每个强连通分量缩成一个点，重新构图，如果新图中有出度为零的点，则该点对应的原图中的点集即为第二问答案。注意排除一个点情况。

<h2>代码</h2>

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 10003;
const int M = 50003;
void read(int &k) {
    k = 0; int fh = 1; char c = getchar();
    for(; c < '0' || c > '9'; c = getchar())
        if (c == '-') fh = -1;
    for(; c >= '0' && c <= '9'; c = getchar())
        k = (k << 1) + (k << 3) + c - '0';
    k = k * fh;
}

bool vis[N], inst[N];
struct node {int from, nxt, to;} E[M];
int DFN[N], low[N], point[N], cnt = 0, col[N], color = 0, st[N], top = 0, n, m, out[N], sum[N];
void tarjan(int x) {
    DFN[x] = low[x] = ++cnt;
    st[++top] = x; vis[x] = inst[x] = 1;
    for(int tmp = point[x]; tmp; tmp = E[tmp].nxt)
        if (!vis[E[tmp].to]) tarjan(E[tmp].to), low[x] = min(low[x], low[E[tmp].to]);
        else if (inst[E[tmp].to]) low[x] = min(low[x], DFN[E[tmp].to]);
    if (low[x] == DFN[x]) {
        int u = 0; ++color;
        while (u != x) {
            u = st[top--];
            col[u] = color;
            inst[u] = 0;
            ++sum[color];
        }
    }
}
void ins(int x, int y) {E[++cnt] = (node) {x, point[x], y}; point[x] = cnt;}
int main() {
    read(n); read(m);
    int u, v;
    for(int i = 1; i <= m; ++i) read(u), read(v), ins(u, v);
    cnt = 0;
    for(int i = 1; i <= n; ++i) if (!vis[i]) tarjan(i);
    for(int i = 1; i <= m; ++i) {
        u = col[E[i].from]; v = col[E[i].to];
        if (u != v) ++out[u];
    }
    int ans = 0, tmp = 0;
    for(int i = 1; i <= color; ++i) if (sum[i] > 1) ++tmp;
    for(int i = 1; i <= color; ++i) {
        if (out[i] == 0) {
            if (ans != 0 || sum[i] == 1) {ans = 0; break;}
            else ans = i;
        }
    }
    printf("%dn", tmp);
    if (ans == 0) puts("-1");
    else {
        for(int i = 1; i <= n; ++i)
            if (col[i] == ans)
                printf("%d ", i);
    }
    return 0;
}