AcWing P164 可达性统计题解

Analysis

这道题我一开始想到的是传递闭包，但是时间复杂度是n³，也开不下30000*30000的数组，所以我想到了拓扑+状态压缩（bitset），从后往前找，把能到达的点能到哪里用位运算赋到上一个中，最后调用.count()输出就好了。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<queue>
 6 #include<bitset>
 7 #define maxn 30010
 8 using namespace std;
 9 inline int read() 
10 {
11     int x=0;
12     bool f=1;
13     char c=getchar();
14     for(; !isdigit(c); c=getchar()) if(c=='-') f=0;
15     for(; isdigit(c); c=getchar()) x=(x<<3)+(x<<1)+c-'0';
16     if(f) return x;
17     return 0-x;
18 }
19 inline void write(int x)
20 {
21     if(x<0){putchar('-');x=-x;}
22     if(x>9)write(x/10);
23     putchar(x%10+'0');
24 }
25 queue<int> q;
26 bitset<maxn> s[maxn];
27 int n,m,cnt,num;
28 int head[2*maxn],rd[maxn],path[maxn];
29 struct node
30 {
31     int v,nex;
32 }edge[2*maxn];
33 inline void add(int u,int v)
34 {
35     cnt++;
36     edge[cnt].v=v;
37     edge[cnt].nex=head[u];
38     head[u]=cnt;
39 }
40 inline void topo()
41 {
42     for(int i=1;i<=n;i++)
43     {
44         if(rd[i]==0)q.push(i);
45     }
46     while(!q.empty())
47     {
48         int t=q.front();
49         q.pop();
50         num++;
51         path[num]=t;
52         for(int i=head[t];i;i=edge[i].nex)
53         {
54             int to=edge[i].v;
55             rd[to]--;
56             if(rd[to]==0)q.push(to);
57         }
58     }
59 }
60 int main()
61 {
62     n=read();m=read();
63     for(int i=1;i<=m;i++)
64     {
65         int x,y;
66         x=read();y=read();
67         add(x,y);
68         rd[y]++;
69     }
70     topo();
71     for(int i=num;i>=1;i--)
72     {
73         int x=path[i];
74         s[x][x]=1;
75         for(int j=head[x];j;j=edge[j].nex)
76         {
77             int to=edge[j].v;
78             s[x]|=s[to];
79         }
80     }
81     for(int i=1;i<=n;i++)
82     {
83         write(s[i].count());
84         printf("
");
85     }
86     return 0;
87 }

请各位大佬斧正（反正我不认识斧正是什么意思）

AcWing P164 可达性统计 题解

Analysis

AcWing P164 可达性统计题解