- 合并两个联通块的最小代价为他们父亲
- 两个结点直接所有路径中最长边的最小值为他们的重构树上 lca
struct edge
{
int x,y,z;
};
bool cmp(edge x,edge y)
{
return x.z<y.z;
}
struct Kruskal
{
int n,m,fa[30010];edge a[60010];
int pa[30010],val[30010];
void init(int _n,int _m)
{
this->n=_n,this->m=_m;
for (int i=1;i<=2*n-1;i++)
fa[i]=i,val[i]=0;
}
int Find(int x)
{
return x==fa[x]?x:fa[x]=Find(fa[x]);
}
void solve()
{
sort(a+1,a+1+m,cmp);
lca.init(2*n-1);int s=n;
for (int i=1;i<=m;i++)
{
int p=Find(a[i].x),q=Find(a[i].y);
if (p!=q)
{
s++;
fa[p]=s,fa[q]=s;
pa[p]=s,pa[q]=s;
val[s]=a[i].z;
}
}
for (int i=1;i<=2*n-1;i++)
lca.Add(i,pa[i]); //加边
}
}kru;- color 二分图染色
- 最小覆盖数 = 最大匹配数
- 最大独立集 = 顶点数 - 二分图匹配数
- DAG 最小路径覆盖数 = 结点数 - 拆点后二分图最大匹配数
struct MaxMatch {
int n;
vector<int> G[N],ans;
int vis[N], left[N], clk,col[N],tag[N];
void init(int n) {
this->n = n;
for(int i=0;i<=n;i++)
G[i].clear();
memset(left, -1, sizeof left);
memset(vis, -1, sizeof vis);
memset(col, -1, sizeof col);
}
bool dfs(int u) {
tag[u]=1;
for (int v: G[u])
if (vis[v] != clk) {
vis[v] = clk;
tag[v]=1;
if (left[v] == -1 || dfs(left[v])) {
left[v] = u;
left[u] = v;
return true;
}
}
return false;
}
void color(int u)
{
for (int v: G[u])
if (col[v]==-1)
{
col[v]=col[u]^1;
color(v);
}
}
int match() {
int ret = 0;
for (clk = 0; clk < n; ++clk)
if (col[clk]==0&&dfs(clk)) ++ret;
return ret;
}
} MM;for (int i=0;i<n;i++)
if (MM.col[i]==-1) MM.col[i]=0,MM.color(i);
printf("%d\n",n-MM.match());
memset(MM.tag,0,sizeof(MM.tag));
for (int i=0;i<n;i++)
if (MM.col[i]==0&&MM.left[i]==-1) MM.dfs(i);
for (int i=0;i<n;i++)
if(!((MM.col[i]==0&&!MM.tag[i])||(MM.col[i]==1&&MM.tag[i])))
printf("%d ",c[i]);- 边的原流量 - 残余网络流量 = 这条边的实际流量
- 残余网络有元素个数不少于
$2$ 的环，则最大流方案不唯一 - 判断边 (x,y) 是否为割边 !edge[].cp&&!DC.BFS(x,y)
- 删除边 (x,y) 退流 DC.go(x,s),DC.go(t,y),edge[].cp=0,edge[+1].cp=0
#define INF 0x3fffffff
struct E
{
int to,cp;
E(int to,int cp):to(to),cp(cp){}
};
struct Dinic
{
static const int M=1E5*5;
int m;
vector<E> edges;
vector<int> G[M];
int d[M];
int cur[M];
void init(int n)
{
for (int i=0;i<=n;i++) G[i].clear();
edges.clear();m=0;
}
void addedge(int u,int v,int cap)
{
edges.push_back(E(v,cap));
edges.push_back(E(u,0));
G[u].push_back(m++);
G[v].push_back(m++);
}
bool BFS(int s,int t)
{
memset(d,0,sizeof d);
queue<int> Q;
Q.push(s);d[s]=1;
while (!Q.empty())
{
int x=Q.front();Q.pop();
for (int& i: G[x])
{
E &e=edges[i];
if (!d[e.to]&&e.cp>0)
{
d[e.to]=d[x]+1;
Q.push(e.to);
}
}
}
return d[t];
}
int DFS(int u,int cp,int s,int t)
{
if (u==t||!cp) return cp;
int tmp=cp,f;
for (int& i=cur[u];i<G[u].size();i++)
{
E& e=edges[G[u][i]];
if (d[u]+1==d[e.to])
{
f=DFS(e.to,min(cp,e.cp),s,t);
e.cp-=f;
edges[G[u][i]^1].cp+=f;
cp-=f;
if (!cp) break;
}
}
return tmp-cp;
}
int go(int s,int t)
{
int flow=0;
while (BFS(s,t))
{
memset(cur,0,sizeof cur);
flow+=DFS(s,INF,s,t);
}
return flow;
}
}DC;
int main()
{
DC.init(n*m+2);
cout<<DC.go(S,T)<<endl;
}#define INF 0x3fffffff
struct E
{
int from,to,cp,v;
E(){}
E(int f,int t,int cp,int v):from(f),to(t),cp(cp),v(v){}
};
struct MCMF
{
int n,m,s,t;
vector<E> edges;
vector<int> G[maxn];
bool inq[maxn]; //是否在队列
int d[maxn]; //Bellman_ford单源最短路径
int p[maxn]; //p[i]表从s到i的最小费用路径上的最后一条弧编号
int a[maxn]; //a[i]表示从s到i的最小残量
void init(int _n, int _s, int _t) {
n = _n; s = _s; t = _t;
for (int i=0;i<=n;i++) G[i].clear();
edges.clear(); m = 0;
}
void addedge(int from, int to, int cap, int cost) {
edges.push_back(E(from, to, cap, cost));
edges.push_back(E(to, from, 0, -cost));
G[from].push_back(m++);
G[to].push_back(m++);
}
bool BellmanFord(int &flow, int &cost) {
for (int i=0;i<=n;i++) d[i] = INF;
memset(inq, 0, sizeof inq);
d[s] = 0, a[s] = INF, inq[s] = true;
queue<int> Q; Q.push(s);
while (!Q.empty()) {
int u = Q.front(); Q.pop();
inq[u] = false;
for (int& idx: G[u]) {
E &e = edges[idx];
if (e.cp && d[e.to] > d[u] + e.v) {
d[e.to] = d[u] + e.v;
p[e.to] = idx;
a[e.to] = min(a[u], e.cp);
if (!inq[e.to]) {
Q.push(e.to);
inq[e.to] = true;
}
}
}
}
if (d[t] == INF) return false;
flow += a[t];
cost += a[t] * d[t];
int u = t;
while (u != s) {
edges[p[u]].cp -= a[t];
edges[p[u] ^ 1].cp += a[t];
u = edges[p[u]].from;
}
return true;
}
int go(int &x) {
int flow = 0, cost = 0;
while (BellmanFord(flow, cost));
x=flow;
return cost;
}
} MM;
int main()
{
MM.init(n+n+2,n+n+1,n+n+2);
int flow,ans;
ans=MM.go(flow);
}给出带权有向图，求节点$1$到所有节点单向联通的最小代价。
const int N=3e5+10;
const LL INF=1e15;
typedef pair<LL,int> P;
struct MTD
{
set<P> G[N];
LL shift[N];
bool vis[N];
int n,m,stk[N],top,fa[N];
int Fa(int x){return fa[x]==x?x:fa[x]=Fa(fa[x]);}
void init(int _n,int _m)
{
n=_n;m=_m;
for (int i=0;i<=n;i++) fa[i]=i;
}
LL solve()
{
LL ans=0;
for (int i=2;i<=n;i++)
{
int u=i;top=0;
while(Fa(u)!=Fa(1))
{
vis[u]=true;stk[top++]=u;
auto it=G[u].begin();
while(it!=G[u].end())
{
int v=it->second;
if (Fa(v)==Fa(u)) it=G[u].erase(it);
else break;
}
if(it==G[u].end())return -INF;
LL lb=it->first;
int v=it->second;
G[u].erase(it);
v=Fa(v);
ans+=lb+shift[u];
shift[u]=-lb;
if(vis[v] && Fa(v)!=Fa(1))
{
int x=v;
while(stk[top-1]!=v)
{
int y=stk[--top];
fa[Fa(y)]=Fa(x);
if(G[x].size()<G[y].size()) G[x].swap(G[y]),swap(shift[x],shift[y]);
for(auto pr: G[y])
G[x].insert(P(pr.first+shift[y]-shift[x],pr.second));
G[y].clear();
}
}
u=v;
}
while(top--) fa[Fa(stk[top])]=1;
}
for (int i=2;i<=n;i++)
if(Fa(i)!=Fa(1)) return -INF;
return ans;
}
}tree;
int n,m;
int main()
{
scanf("%d%d",&n,&m);
tree.init(n,m);
int u,v,w;
for (int i=0;i<m;i++)
scanf("%d%d%d",&u,&v,&w),tree.G[v].insert(P(w,u));
LL ans=tree.solve();
if (ans==-INF) puts("NO");else printf("%lld\n",ans);
}- S是起点。
- dt 存下了支配树的信息，如果$x$是$y$的祖先，那么$x$是起点到$y$的必经点。
-
$idom[x]$ 是节点$x$的最近必经点
vector<int> G[N],rG[N];
vector<int> dt[N];
struct tl
{
int fa[N],idx[N],clk,ridx[N];
int c[N],best[N],semi[N],idom[N];
void init(int n)
{
clk=0;
fill(c,c+n+1,-1);
for (int i=1;i<=n;i++) dt[i].clear();
for (int i=1;i<=n;i++) semi[i]=best[i]=i;
fill(idx,idx+n+1,0);
for (int u=1;u<=n;u++)
for (int v:G[u])
rG[v].push_back(u);
}
void dfs(int u)
{
idx[u]=++clk;ridx[clk]=u;
for (int& v:G[u]) if (!idx[v]){fa[v]=u;dfs(v);}
}
int fix(int x)
{
if (c[x]==-1) return x;
int &f=c[x],rt=fix(f);
if (idx[semi[best[x]]]>idx[semi[best[f]]]) best[x]=best[f];
return f=rt;
}
void go(int rt)
{
dfs(rt);
for (int i=clk;i>1;i--)
{
int x=ridx[i],mn=clk+1;
for (int& u:rG[x])
{
if (!idx[u]) continue;
fix(u);mn=min(mn,idx[semi[best[u]]]);
}
c[x]=fa[x];
dt[semi[x]=ridx[mn]].push_back(x);
x=ridx[i-1];
for (int& u: dt[x])
{
fix(u);
if (semi[best[u]]!=x) idom[u]=best[u];
else idom[u]=x;
}
dt[x].clear();
}
for (int i=2;i<=clk;i++)
{
int u=ridx[i];
if (idom[u]!=semi[u]) idom[u]=idom[idom[u]];
dt[idom[u]].push_back(u);
}
}
}tree;
int main()
{
int x,p,q;
scanf("%d%d%d",&n,&m,&x);
for (int i=1;i<=m;i++)
{
scanf("%d%d",&p,&q);
G[p].push_back(q);
}
tree.init(n);
tree.go(x);
}- 邻接表编写
- 边从0开始标号，点从1开始
- init()清空，go()搞好id[]，也就是缩点编号
vector<int> u, v;
namespace EDCC {
vector<int> dfn, low, id;
vector<bool> insta;
stack<int> sta;
int edcc;
vector< vector< pair<int, int> > > G;
int clk;
void init(int n) {
clk = 0;
dfn.resize(n+1);
fill(dfn.begin(), dfn.end(), 0);
low.resize(n+1);
fill(low.begin(), low.end(), 0);
G.resize(n+1);
FOR (i, 1, n+1)
G[i].clear();
id.resize(n+1);
fill(id.begin(), id.end(), 0);
while (!sta.empty()) sta.pop();
insta.resize(n+1);
fill(insta.begin(), insta.end(), 0);
edcc = 0;
}
void add(int a, int b, int id) {
if (a != b) {
G[a].push_back(make_pair(b, id));
G[b].push_back(make_pair(a, id));
}
}
void tarjan(int now, int fa, int reid) {
// dbg("tarjan", now);
dfn[now] = ++clk;
low[now] = dfn[now];
insta[now] = 1;
sta.push(now);
for (const pii &e:G[now]) {
int nt = e.first, eid = e.second;
if (eid == reid) continue;
if (!dfn[nt]) {
tarjan(nt, now, eid);
low[now] = min(low[nt], low[now]);
} else if (insta[nt])
low[now] = min(dfn[nt], low[now]);
}
if (dfn[now] == low[now]) {
++edcc;
while (!sta.empty()) {
int v = sta.top();
id[v] = edcc;
insta[v] = 0;
sta.pop();
if (v == now) break;
}
}
}
void go(int n) {
FOR (i, 0, sz(u)) {
add(u[i], v[i], i);
}
FOR (i, 1, n+1) {
if (!dfn[i]) {
if (!sta.empty()) {
while(1){}
}
tarjan(i, i, -1);
}
}
}
}
#define M 10100
#define INF 0x3f3f3f3f
int n,m,q,cnt;
map<int,int> f[M];
vector<int> belong[M];
int dis[M];
vector<int> rings[M];
int size[M];
map<int,int> dist[M];
void Add(int x,int y,int z)
{
if( f[x].find(y)==f[x].end() )
f[x][y]=INF;
f[x][y]=min(f[x][y],z);
}
namespace Cactus_Graph{
int fa[M<<1][16],dpt[M<<1];
pair<int,int> second_lca;
int Get_Depth(int x)
{
if(!fa[x][0]) dpt[x]=1;
if(dpt[x]) return dpt[x];
return dpt[x]=Get_Depth(fa[x][0])+1;
}
void Pretreatment()
{
int i,j;
for(j=1;j<=15;j++)
{
for(i=1;i<=cnt;i++)
fa[i][j]=fa[fa[i][j-1]][j-1];
for(i=n+1;i<=n<<1;i++)
fa[i][j]=fa[fa[i][j-1]][j-1];
}
for(i=1;i<=cnt;i++)
Get_Depth(i);
for(i=n+1;i<=n<<1;i++)
Get_Depth(i);
}
int LCA(int x,int y)
{
int j;
if(dpt[x]<dpt[y])
swap(x,y);
for(j=15;~j;j--)
if(dpt[fa[x][j]]>=dpt[y])
x=fa[x][j];
if(x==y) return x;
for(j=15;~j;j--)
if(fa[x][j]!=fa[y][j])
x=fa[x][j],y=fa[y][j];
second_lca=make_pair(x,y);
return fa[x][0];
}
}
void Tarjan(int x)
{
static int dpt[M],low[M],T;
static int stack[M],top;
map<int,int>::iterator it;
dpt[x]=low[x]=++T;
stack[++top]=x;
for(it=f[x].begin();it!=f[x].end();it++)
{
if(dpt[it->first])
low[x]=min(low[x],dpt[it->first]);
else
{
Tarjan(it->first);
if(low[it->first]==dpt[x])
{
int t;
rings[++cnt].push_back(x);
belong[x].push_back(cnt);
Cactus_Graph::fa[cnt][0]=n+x;
do{
t=stack[top--];
rings[cnt].push_back(t);
Cactus_Graph::fa[n+t][0]=cnt;
}while(t!=it->first);
}
low[x]=min(low[x],low[it->first]);
}
}
}
void DFS(int x)
{
vector<int>::iterator it,_it;
static int stack[M];int i,j,top=0;
for(it=rings[x].begin();it!=rings[x].end();it++)
stack[++top]=*it;
stack[++top]=*rings[x].begin();
for(i=1;i<top;i++)
{
int p1=stack[i],p2=stack[i+1];
size[x]+=f[p1][p2];
if(i!=top-1)
dist[x][p2]=dist[x][p1]+f[p1][p2];
}
i=2;j=top-1;
while(i<=j)
{
if(dis[stack[i-1]]+f[stack[i-1]][stack[i]]<dis[stack[j+1]]+f[stack[j+1]][stack[j]])
dis[stack[i]]=dis[stack[i-1]]+f[stack[i-1]][stack[i]],i++;
else
dis[stack[j]]=dis[stack[j+1]]+f[stack[j+1]][stack[j]],j--;
}
for(_it=rings[x].begin(),_it++;_it!=rings[x].end();_it++)
for(it=belong[*_it].begin();it!=belong[*_it].end();it++)
DFS(*it);
}
int main()
{
using namespace Cactus_Graph;
int i,x,y,z;
cin>>n>>m>>q;
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
Add(x,y,z);Add(y,x,z);
}
Tarjan(1);
Pretreatment();
vector<int>::iterator it;
for(it=belong[1].begin();it!=belong[1].end();it++)
DFS(*it);
for(i=1;i<=q;i++)
{
scanf("%d%d",&x,&y);
int lca=LCA(n+x,n+y);
if(lca>n) printf("%d\n",dis[x]+dis[y]-2*dis[lca-n]);
else
{
int ans=dis[x]+dis[y]-dis[second_lca.first-n]-dis[second_lca.second-n];
int temp=abs(dist[lca][second_lca.first-n]-dist[lca][second_lca.second-n]);
ans+=min(temp,size[lca]-temp);
printf("%d\n",ans);
}
}
return 0;
}输入的第一行包括两个整数
int read(){
char c;int s=0,t=1;
while(!isdigit(c=getchar()))if(c=='-')t=-1;
do{s=s*10+c-'0';}while(isdigit(c=getchar()));
return s*t;
}
const int maxn=100010,maxm=20000010;
struct edge{int v,from;}e[maxm];
int first[maxn],tot,fa[maxn],a[maxn],f[maxn],q[maxn],dfn[maxn],low[maxn],ans,dfsnum=0,n,m;
void insert(int u,int v){tot++;e[tot].v=v;e[tot].from=first[u];first[u]=tot;}
void solve(int A,int B){
int cnt=0;
for(int i=B;i!=A;i=fa[i])a[++cnt]=f[i];a[++cnt]=f[A];
for(int i=1;i<=cnt/2;i++)swap(a[i],a[cnt-i+1]);
for(int i=cnt+1;i<=cnt+(cnt>>1);i++)a[i]=a[i-cnt];
int head=0,tail=1;q[head]=1;
for(int i=2;i<=cnt+(cnt>>1);i++){
if(head<tail&&i-q[head]>cnt/2)head++;
ans=max(ans,a[i]+a[q[head]]+i-q[head]);
while(head<tail&&a[i]-i>=a[q[tail-1]]-q[tail-1])tail--;
q[tail++]=i;
}
for(int i=2;i<=cnt;i++)f[A]=max(f[A],a[i]+min(i-1,cnt-i+1));
}
void dfs(int x,int father){
dfn[x]=low[x]=++dfsnum;f[x]=0;
for(int i=first[x];i;i=e[i].from)if(e[i].v!=father){
int y=e[i].v;
if(!dfn[y]){
fa[y]=x;
dfs(y,x);
low[x]=min(low[x],low[y]);
}else low[x]=min(low[x],dfn[y]);
if(low[y]>dfn[x]){
ans=max(ans,f[x]+f[y]+1);
f[x]=max(f[x],f[y]+1);
}
}
for(int i=first[x];i;i=e[i].from)
if(e[i].v!=father&&fa[e[i].v]!=x&&dfn[e[i].v]>dfn[x])solve(x,e[i].v);
}
int main(){
n=read();m=read();
for(int i=1;i<=m;i++){
int k=read(),u=read();
for(int j=2;j<=k;j++){
int v=read();
insert(u,v);insert(v,u);
u=v;
}
}
ans=0;
dfs(1,0);
printf("%d",ans);
return 0;
}现给定一棵仙人掌，每条边有一个正整数权值，每次给
对于每一个询问包含
typedef long long ll;
using namespace std;
const int MAXN=6e5+10;
int dfn[MAXN],low[MAXN],N,M,cnt,tot;
int fa[MAXN][20],dpt[MAXN],S[MAXN],seq[MAXN],q[MAXN],vis[MAXN],top,ncnt;
ll ringDis[MAXN],rLen[MAXN],rtDis[MAXN],f[MAXN],rD[MAXN<<1],rF[MAXN<<1],ans;
vector<int> G[MAXN],g[MAXN]; vector<ll> W[MAXN]; map<int,int> e[MAXN];
void add(int u,int v,int z)
{
if(!e[u].count(v)) e[u][v]=z;
else e[u][v]=min(e[u][v],z);
}
void tarjan(int u,int la)
{
int i,v; S[++top]=u;
dfn[u]=low[u]=++tot;
map<int,int> :: iterator it;
for(it=e[u].begin();it!=e[u].end();it++)
{
v=it->first;
if(v==la) continue;
if(!dfn[v])
{
ringDis[v]=ringDis[u]+it->second;
tarjan(v,u);
low[u]=min(low[u],low[v]);
if(dfn[u]<=low[v])
{
rLen[++ncnt]=ringDis[S[top]]-ringDis[u]+e[S[top]][u];
while(true)
{
int x=S[top--];
G[ncnt].push_back(x);
W[ncnt].push_back(min(ringDis[x]-ringDis[u],rLen[ncnt]-ringDis[x]+ringDis[u]));
if(x==v) break;
}
G[u].push_back(ncnt);W[u].push_back(0);
}
}
else
low[u]=min(low[u],dfn[v]);
}
}
void dfs(int u)
{
int i,v;
dfn[u]=++tot;
for(i=1;fa[fa[u][i-1]][i-1];i++)
fa[u][i]=fa[fa[u][i-1]][i-1];
for(i=0;i<G[u].size();i++)
{
v=G[u][i];
dpt[v]=dpt[u]+1;
rtDis[v]=rtDis[u]+W[u][i];
fa[v][0]=u;
dfs(v);
}
}
int get_kth(int u,int k)
{
for(int i=19;~i;i--)
if(k>>i&1)
u=fa[u][i];
return u;
}
int find_lca(int u,int v)
{
if(dpt[u]<dpt[v]) swap(u,v);
u=get_kth(u,dpt[u]-dpt[v]);
if(u==v) return u;
for(int i=19;~i;i--)
if(fa[u][i]!=fa[v][i])
u=fa[u][i],v=fa[v][i];
return fa[u][0];
}
void solve(int P)
{
int i,l,r;
for(i=1;i<=tot;i++)
rF[i]=f[seq[i]],rD[i]=ringDis[seq[i]];
rD[tot+1]=rD[1]+rLen[P]; rF[tot+1]=rF[1];
for(i=tot+2;i<=2*tot;i++)
rD[i]=rD[i-1]+rD[i-tot]-rD[i-tot-1],rF[i]=rF[i-tot];
q[l=r=1]=1;
for(i=2;i<=2*tot;i++)
{
while(l<=r&&2*rD[i]>rLen[P]+2*rD[q[l]]) l++;
if(l<=r) ans=max(ans,rD[i]-rD[q[l]]+rF[i]+rF[q[l]]);
while(l<=r&&rF[i]-rD[i]>=rF[q[r]]-rD[q[r]]) r--;
q[++r]=i;
}
}
void dp(int u)
{
int i,v; f[u]=0;
if(u<=N)
for(i=0;i<g[u].size();i++)
{
v=g[u][i];
dp(v);
if(vis[u]) ans=max(ans,f[u]+f[v]+rtDis[v]-rtDis[u]);
f[u]=max(f[u],f[v]+rtDis[v]-rtDis[u]);
vis[u]=1;
}
else
{
for(i=0;i<g[u].size();i++)
dp(g[u][i]);
tot=0;
for(i=0;i<g[u].size();i++)
{
v=g[u][i];
f[u]=max(f[u],f[v]+rtDis[v]-rtDis[u]);
int x=get_kth(v,dpt[v]-dpt[u]-1);
f[x]=f[v]+rtDis[v]-rtDis[x]; seq[++tot]=x;
}
std::reverse(seq+1,seq+1+tot);
solve(u);
}
vis[u]=0;
}
void Push(int u) { g[u].clear(); S[++top]=u; }
bool cmp(int u,int v) { return dfn[u]<dfn[v]; }
int main()
{
int i,u,v,z;
scanf("%d%d",&N,&M);ncnt=N;
for(i=1;i<=M;i++)
{
scanf("%d%d%d",&u,&v,&z);
add(u,v,z); add(v,u,z);
}
tarjan(1,0); tot=0;
dfs(1);
scanf("%d",&M);
while(M--)
{
ans=0;
scanf("%d",&v);
for(i=1;i<=v;i++)
scanf("%d",seq+i),vis[seq[i]]=1;
sort(seq+1,seq+v+1,cmp); v=unique(seq+1,seq+v+1)-seq-1;
top=0; Push(1);
for(i=1+(seq[1]==1);i<=v;i++)
{
u=find_lca(seq[i],S[top]);
while(dpt[u]<dpt[S[top]])
{
if(dpt[u]>=dpt[S[top-1]])
{
z=S[top--];
if(u!=S[top]) Push(u);
g[u].push_back(z);
break;
}
g[S[top-1]].push_back(S[top]); top--;
}
Push(seq[i]);
}
for(;top>1;top--) g[S[top-1]].push_back(S[top]);
dp(1);
printf("%lld\n",ans);
}
return 0;
}从
对于
typedef unsigned long long ll;
typedef vector<int> vi;
const int mod=998244353,i2=(mod+1)/2,inf=2147483647;
int mul(int a,int b){return(ll)a*b%mod;}
void inc(int&a,int b){(a+=b)>=mod?a-=mod:0;}
int pow(int a,int b){
int s=1;
while(b){
if(b&1)s=mul(s,a);
a=mul(a,a);
b>>=1;
}
return s;
}
int rev[270010],N,iN;
int*w[18];
void pre(int n){
int i,j,k,t;
for(N=1,k=0;N<n;N<<=1)k++;
for(i=0;i<N;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(k-1));
for(i=2,k=0;i<=N;i<<=1,k++){
if(w[k])continue;
w[k]=new int[i+1];
t=pow(3,(mod-1)/i);
w[k][0]=1;
for(j=1;j<=i;j++)w[k][j]=mul(w[k][j-1],t);
}
iN=pow(i2,k);
}
void ntt(int*a,int on){
int i,j,k,f,i2;
ll t1,t2;
static ll b[270010];
for(i=0;i<N;i++)b[i]=a[rev[i]];
for(i=2,f=0;i<=N;i<<=1,f++){
for(j=0;j<N;j+=i){
i2=i/2+j;
for(k=0;k<i>>1;k++){
t1=b[j+k];
t2=b[i2+k]*w[f][on==1?k:i-k]%mod;
b[j+k]=t1+t2;
b[i2+k]=t1-t2+mod;
}
}
}
for(i=0;i<N;i++)a[i]=b[i]%mod;
if(on==-1){
for(i=0;i<N;i++)a[i]=mul(a[i],iN);
}
}
int ta[270010],tb[270010];
vi operator*(vi a,vi b){
int n=a.size()+b.size()-1;
pre(n);
memset(ta,0,N<<2);
memset(tb,0,N<<2);
memcpy(ta,&a[0],a.size()<<2);
memcpy(tb,&b[0],b.size()<<2);
ntt(ta,1);
ntt(tb,1);
for(int i=0;i<N;i++)ta[i]=mul(ta[i],tb[i]);
ntt(ta,-1);
return vi(ta,ta+n);
}
void inc(vi&a,vi b,int n){
a.resize(max(a.size(),b.size()+n));
for(int i=0;i<(int)b.size();i++)inc(a[i+n],b[i]);
}
vi operator+(vi a,vi b){
inc(a,b,0);
return a;
}
vi p[200010];
int m;
vi solve(int l,int r){
if(l==r)return p[l];
int mid=(l+r)>>1;
return solve(l,mid)*solve(mid+1,r);
}
int n;
namespace t{
int h[200010],nex[400010],to[400010],M;
void ins(int a,int b){
M++;
to[M]=b;
nex[M]=h[a];
h[a]=M;
}
int fa[200010],ch[200010],rk[200010];
void add(int a,int b){
ins(a,b);
ins(b,a);
fa[b]=a;
ch[a]++;
}
bool vis[200010];
#define ok to[i]!=fa&&!vis[to[i]]
int siz[200010];
void dfs1(int fa,int x){
siz[x]=1;
for(int i=h[x];i;i=nex[i]){
if(ok){
dfs1(x,to[i]);
siz[x]+=siz[to[i]];
}
}
}
int mn,cn,n;
void dfs2(int fa,int x){
int i,k=n-siz[x];
for(i=h[x];i;i=nex[i]){
if(ok){
dfs2(x,to[i]);
k=max(k,siz[to[i]]);
}
}
if(k<mn){
mn=k;
cn=x;
}
}
vi solve(int x){
dfs1(0,x);
n=siz[x];
mn=inf;
dfs2(0,x);
x=cn;
vis[x]=1;
int i,u;
vi s,t;
bool up=0;
s={0};
for(i=h[x];i;i=nex[i]){
if(!vis[to[i]]){
if(to[i]!=fa[x]){
t=solve(to[i]);
if(x<=::n)
inc(s,t,1);
else{
inc(s,t,rk[to[i]]-1);
inc(s,t,ch[x]-rk[to[i]]);
}
}else
up=1;
}
}
if(x<=::n)inc(s[0],1);
if(!up)return s;
m=0;
for(u=x;!vis[fa[u]];u=fa[u]){
if(fa[u]<=::n)
p[++m]={0,1};
else{
t=vi(max(rk[u]-1,ch[fa[u]]-rk[u])+1,0);
t[rk[u]-1]++;
t[ch[fa[u]]-rk[u]]++;
p[++m]=t;
}
}
return solve(fa[x])+::solve(1,m)*s;
}
vi work(){
int x,i,j;
for(x=1;x<=N;x++){
j=0;
for(i=h[x];i;i=nex[i]){
if(to[i]!=fa[x])rk[to[i]]=++j;
}
}
vis[0]=1;
return solve(1);
}
}
namespace g{
int h[100010],nex[400010],to[400010],M=1;
void ins(int a,int b){
M++;
to[M]=b;
nex[M]=h[a];
h[a]=M;
}
void add(int a,int b){
ins(a,b);
ins(b,a);
}
int dfn[100010],low[100010],st[100010],tp;
void dfs(int fa,int x){
dfn[x]=low[x]=++M;
st[++tp]=x;
for(int i=h[x];i;i=nex[i]){
if(!dfn[to[i]]){
dfs(i,to[i]);
low[x]=min(low[x],low[to[i]]);
if(low[to[i]]>dfn[x])t::add(x,st[tp--]);
if(low[to[i]]==dfn[x]){
N++;
while(st[tp]!=to[i])t::add(N,st[tp--]);
t::add(N,st[tp--]);
t::add(x,N);
}
}else if(i^fa^1)
low[x]=min(low[x],dfn[to[i]]);
}
}
void work(){
M=0;
dfs(0,1);
}
}
int main(){
int m,i,x,y;
scanf("%d%d",&n,&m);
while(m--){
scanf("%d%d",&x,&y);
g::add(x,y);
}
N=n;
g::work();
vi s=t::work();
s.resize(n);
for(i=1;i<n;i++)printf("%d\n",s[i]);
}- 弦是环上连接两个不相邻的点的边。
- 任意一个长度大于
$3$ 的环上一定有一条弦。 - 弦图的诱导子图都是弦图。
- 一个结点
$v$ 和与$v$ 相邻的结点形成的诱导子图为一个团，则$v$ 是单纯点。 - 弦图至少有一个单纯点，不是完全图的弦图至少有两个不相邻的单纯点。
- 一个图是弦图等价于它有完美消除序列。
- 最大团 = 最小染色
- 最大点独立集 = 最小团覆盖
最小染色数量
#define rep(i,k,n) for(int i=(k);i<=(n);i++)
#define rep0(i,n) for(int i=0;i<(n);i++)
#define red(i,k,n) for(int i=(k);i>=(n);i--)
#define sqr(x) ((x)*(x))
#define clr(x,y) memset((x),(y),sizeof(x))
#define pb push_back
#define mod 1000000007
const int maxn=10010;
const int maxm=4000010;
struct List
{
int v,next;
}list[maxm];
int eh[maxn],tot,mh[maxn];
inline void add(int h[],int u,int v)
{
list[tot].v=v;
list[tot].next=h[u];
h[u]=tot++;
}
int n,m,best,q[maxn],f[maxn],color[maxn],mark[maxn];
bool vis[maxn];
void MCS()
{
clr(mh,-1);clr(vis,0);clr(f,0);
rep(i,1,n)add(mh,0,i);
best=0;
red(j,n,1)
{
while(1)
{
int i;
for(i=mh[best];~i;i=list[i].next)
{
if(!vis[list[i].v])break;
else mh[best]=list[i].next;
}
if(~i)
{
int x=list[i].v;
q[j]=x;vis[x]=1;
for(i=eh[x];~i;i=list[i].next)
{
int v=list[i].v;
if(vis[v])continue;
f[v]++;
add(mh,f[v],v);
best=max(best,f[v]);
}
break;
}
else best--;
}
}
}
int main()
{
scanf("%d%d",&n,&m);
int u,v;
clr(eh,-1);tot=0;
rep(i,1,m)
{
scanf("%d%d",&u,&v);
add(eh,u,v);
add(eh,v,u);
}
MCS();
clr(mark,0);clr(color,0);
int ans=0;
red(j,n,1)
{
for(int i=eh[q[j]];~i;i=list[i].next)mark[color[list[i].v]]=j;
int i;
for(i=1;mark[i]==j;i++);
color[q[j]]=i;
ans=max(ans,i);
}
printf("%d\n",ans);
return 0;
}