cpp1.cpp

求强连通分量

#include <stdio.h>
#include <string.h>
#define G_size 100000
#define V_size 11000
 
typedef struct Graph
{
    int id;
    int next;
} Graph;
 
typedef struct Edge
{
    int s;
	int e;
} Edge;
 
Edge E[G_size];
Graph GA[G_size], GT[G_size];
int N, M;
int G_end;//最后一个节点的序号
int order[V_size], id[V_size], vis[V_size], in[V_size];//order[]:记录dfs过程结束访问点的顺序
int cnt, scnt, pos;
 
void Insert(int s, int e) //建立原图和逆图
{
    int p;
    p = s;
    while (GA[p].next)//建立原图
        p = GA[p].next;
    GA[G_end].id = e;
    GA[p].next = G_end;
 
    p = e;
    while (GT[p].next)//建立逆图
        p = GT[p].next;
    GT[G_end].id = s;
    GT[p].next = G_end;
 
    G_end++;
}
 
void DFST(int x) //对逆图进行搜索
{
    int p, q;
    vis[x] = 1;//置已访问标记
    p = GT[x].next; 
while (p)//当邻接顶点存在时循环
    {
        q = GT[p].id;
        if (!vis[q])//是未访问的结点
            DFST(q);//递归搜索
        p = GT[p].next;//取下一个邻接顶点
    }
    order[cnt++] = x;
}
 
void DFSA(int x) //对原图进行搜索
{
    int p, q;
    vis[x] = 1;//置已访问标记
    id[x] = cnt;
    p = GA[x].next;
    while (p)
    {
        q = GA[p].id;
        if (!vis[q])//是未访问的结点
            DFSA(q);//递归搜索
        p = GA[p].next;//取下一个邻接顶点
   }
}
 
void Solve() //主要过程
{
    int s, e;
    int i;
 
    memset(GA, 0, sizeof(GA));//初始化
    memset(GT, 0, sizeof(GT));//初始化
    memset(E, 0, sizeof(E));//初始化
    G_end = N + 1;
 
    for (i = 0; i < M; i++)
    {
        scanf("%d %d", &s, &e);//s是权值，e是序号
        E[i].s = s - 1;
        E[i].e = e - 1;
        Insert(s - 1, e - 1);
    }
 
    memset(vis, 0, sizeof(vis));//初始化
    cnt = 0;
    for (i = 0; i < N; i++)
    {
        if (!vis[i])
        {
            DFST(i);
        }
    }
 
    memset(vis, 0, sizeof(vis)); //初始化
	cnt = 0;
    for (i = N - 1; i >= 0; i--)
    {
        if (!vis[order[i]])
        {
            DFSA(order[i]);
            cnt++;
        }
    }
 
    for (i = 0; i < M; i++)
    {
        s = id[E[i].s];
        e = id[E[i].e];
        if (s != e)
        {
            in[s]++;
        }
    }
    scnt = cnt;
    cnt = 0;
    for (i = 0; i < scnt; i++)
    {
        if (in[i] == 0)
        {
            pos = i;
            cnt++;
        }
    }
    if (cnt != 1)
    {
        printf("0\n");
    }
    else
    {
        cnt = 0;
        for (i = 0; i < N; i++)
        {
            if (in[id[i]] == pos)
            {
                cnt++;
            }
        } printf("%d\n", cnt);
    }
}
 
int main()
{
    while (EOF != scanf("%d %d", &N, &M))
        Solve();
    return 0;
}