看到有两个新的模板题,想着复习一下但是就 85pts 一直 WA:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <stack>
#define init(x) memset (x,0,sizeof (x))
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
using namespace std;
const int MAXN = 5e5 + 5;
const int MAXM = 2e6 + 5;
const int MOD = 1e9 + 7;
inline int read ();
int n,m,cnt,times,bcc_cnt;
int head[MAXM << 1],to[MAXM << 1],nxt[MAXM << 1],dfn[MAXN],low[MAXN];
void add (int u,int v);
void dfs (int u,int fa);
stack <int> s;
vector <int> bcc[MAXN];
int main ()
{
// freopen (".in","r",stdin);
// freopen ("1.out","w",stdout);
n = read ();m = read ();
for (int i = 1;i <= m;++i)
{
int u = read (),v = read ();
add (u,v);add (v,u);
}
for (int i = 1;i <= n;++i)
if (!dfn[i]) dfs (i,-1);
printf ("%d\n",bcc_cnt);
for (int i = 1;i <= bcc_cnt;++i)
{
printf ("%d ",bcc[i].size ());
for (int j = 0;j < bcc[i].size ();++j) printf ("%d ",bcc[i][j]);
puts ("");
}
return 0;
}
inline int read ()
{
int s = 0;int f = 1;
char ch = getchar ();
while ((ch < '0' || ch > '9') && ch != EOF)
{
if (ch == '-') f = -1;
ch = getchar ();
}
while (ch >= '0' && ch <= '9')
{
s = s * 10 + ch - '0';
ch = getchar ();
}
return s * f;
}
void add (int u,int v)
{
to[++cnt] = v;
nxt[cnt] = head[u];
head[u] = cnt;
}
void dfs (int u,int fa)
{
dfn[u] = low[u] = ++times;
s.push (u);
for (int i = head[u];i;i = nxt[i])
{
int v = to[i];
if (!dfn[v])
{
dfs (v,u);//dfs (v,i)
low[u] = min (low[u],low[v]);
}
else if (v != fa && dfn[v] < dfn[u]) low[u] = min (low[u],dfn[v]);//i != (fa ^ 1)
}
if (low[u] == dfn[u])
{
++bcc_cnt;
while (1)
{
int x = s.top ();s.pop ();
bcc[bcc_cnt].push_back (x);
if (u == x) break;
}
}
}
为啥这样只能拿 85pts?错在哪里了呢?
改成初始 cnt = 1,打注释的地方变为 i 而不是 v 后才能过,不是很理解,求解释!