CSP前模板复习

#include 
#include 
#include 
using namespace std;

const int N = 1e4 + 1e3;

int n, m, cnt, dfn[N], low[N], inq[N];

int stk[N], tp, c[N], cnt_c, sz[N];

vector ed[N], ed_c[N];

void tarjan(int u) {
    inq[u] = 1;
    stk[++tp] = u;
    dfn[u] = low[u] = ++cnt;
    for (int i = 0, up = ed[u].size(); i < up; ++i) {
        if (!dfn[ed[u][i]]) {
            tarjan(ed[u][i]);
            low[u] = min(low[u], low[ed[u][i]]);
        }
        else if (inq[ed[u][i]])
            low[u] = min(low[u], low[ed[u][i]]);
    }
    if (dfn[u] == low[u]) {
        ++cnt_c;
        while (1) {
            c[stk[tp]] = cnt_c;
            inq[stk[tp]] = 0;
            sz[cnt_c]++;
            tp--;
            if (stk[tp + 1] == u) break;
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        ed[u].push_back(v);
    }
    for (int i = 1; i <= n; ++i) 
        if (!dfn[i]) tarjan(i);
    for (int i = 1; i <= n; ++i) {
        for (int j = 0, up = ed[i].size(); j < up; ++j) {
            if (c[i] != c[ed[i][j]]) {
                ed_c[c[i]].push_back(c[ed[i][j]]);
            }
        }
    }
    int flag =0, ans = 0;
    for (int i = 1; i <= cnt_c; ++i) {
        if (!ed_c[i].size()) flag++, ans = sz[i];
    }
    if (flag > 1) return puts("0"), 0;
    printf("%d\n", ans);
}

```
#include 
#include 
#include 
#include 
using namespace std;

const int N = 1e5 + 5;

int dfn[N], low[N], cnt, n, m;

int stk[N], tp, root, cut[N], cnt_DCC;

vector ed[N], cut_node, DCC[N];


void tarjan(int u) {
    int flag = 0;
    dfn[u] = low[u] = ++ cnt;
    stk[++tp] = u;
    for (int i = 0, up = ed[u].size(); i < up; ++i) {
        if (!dfn[ed[u][i]]) {
            tarjan(ed[u][i]);
            low[u] = min(low[u], low[ed[u][i]]);
            if (low[ed[u][i]] >= dfn[u]) {
                ++flag;
                if (root != u || flag > 1) {
                    cut[u] = 1;
                }
                ++cnt_DCC;
                while (1) {
                    DCC[cnt_DCC].push_back(stk[tp]);
                    tp--;
                    if (stk[tp + 1] == ed[u][i])
                        break;
                }
                DCC[cnt_DCC].push_back(u);
            }
        }
        else
            low[u] = min(low[u], dfn[ed[u][i]]);
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        ed[u].push_back(v);
        ed[v].push_back(u);
    }
    for (int i = 1; i <= n; ++i) if (!dfn[i])
        tarjan(root = i);
    for (int i = 1; i <= n; ++i)
        if (cut[i]) cut_node.push_back(i);
    printf("%d\n", (int)cut_node.size());
    for (int i = 0, up = cut_node.size(); i < up; ++i)
        printf("%d ", cut_node[i]);
    puts("");
    for (int i = 1; i <= cnt_DCC; ++i) {
        printf("e-DCC %d ", i);
        for (int j = 0, up = DCC[i].size(); j < up; ++j)
            printf("%d ", DCC[i][j]);
        puts("");
    }
}
```

 

```
#include 
#include size=
#include 
#include 
#include 
using namespace std;
typedef long long LL;

const int N = 1e4 + 5, M = 1e6;

int head[N], tot, n, m,  S, vis[N];
LL dis[N];

queue que;

struct edge {
    int nxt, to, w;
}e[M];

void add(int u, int v, int w) {
    e[++tot].nxt = head[u];
    e[tot].to = v;
    e[tot].w = w;
    head[u] = tot;
}

void SPFA() {
    dis[S] = 0;
    que.push(S);
    for (int u; !que.empty(); ) {
        u = que.front(); que.pop();
        vis[u] = 0;
        for (int i = head[u]; i; i = e[i].nxt) {
            int nt = e[i].to;
            if (dis[nt] > dis[u] + e[i].w) {
                dis[nt] = dis[u] + e[i].w;
                if (!vis[nt]) que.push(nt), vis[nt] = 1;
            }
        }
    }
}

int main()
{
   scanf("%d%d%d", &n, &m, &S);
   for (int i = 1; i <= m; ++i) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, w);
   }
   memset(dis, 120, sizeof(dis));
   SPFA();
   for (int i = 1; i <= n; ++i) {
       if (dis[i] == dis[0])
           printf("%lld ", 2147483647LL);
       else printf("%lld ", dis[i]);
   }
}

```