성 선발 전문 연습 POI2008BLO
이것은 명백한 분할점이다.
그리고siz자수를 매거하고,
정난즉반의 사상을 이용하여 답을 구하다
n*n-sigma SIZi^2
#include
#include
#include
#include
#include
#include
using namespace std;
typedef int INT;
#define int long long
int n,m;
const int N=5e5+100;
struct Front_star{
int u,v,nxt;
}e[N*3];
int cnt=0;
int first[N]={0};
void add(int u,int v){
cnt++;
e[cnt].u=u;
e[cnt].v=v;
e[cnt].nxt=first[u];
first[u]=cnt;
}
int color[N]={0};
int scc=0;
int dfn[N]={0};
int low[N]={0};
int dep[N]={0};
int SIZE[N]={0};
int pd[N]={0};
int siz=0;
int son=0;
stack S;
void tarjan(int u,int fat){
siz++;
dfn[u]=siz;
low[u]=siz;
SIZE[u]=1;
dep[u]=dep[fat]+1;
S.push(u);
for(int i=first[u];i;i=e[i].nxt){
int v=e[i].v;
if(fat==v)
continue;
if(!dfn[v]){
tarjan(v,u);
low[u]=min(low[u],low[v]);
SIZE[u]+=SIZE[v];
if(low[v]>=dfn[u]){
pd[u]=1;
// if(dfn[u]==1)
// son++;
}
}
else{
low[u]=min(low[u],dfn[v]);
}
}
}
INT main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=m;i++){
int u,v;
scanf("%lld%lld",&u,&v);
add(u,v);
add(v,u);
}
tarjan(1,0);
// if(son==1)
for(int u=1;u<=n;u++){
if(pd[u]){
int sum1=1;
int sum2=1;
for(int i=first[u];i;i=e[i].nxt){
int v=e[i].v;
if(dep[v]==dep[u]+1&&low[v]>=dfn[u]){
sum1+=SIZE[v];
sum2+=SIZE[v]*SIZE[v];
}
}
sum2+=(n-sum1)*(n-sum1);
cout< 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
01 가방, 완전 가방, 다중 가방 dp(동적 기획 입문 dp)01 가방은 2진법으로 직접 표시할 수 있지만 데이터 양이 너무 많으면 시간을 초과하는 것이 폭력이다.01 가방의 사상은 바로 이 물품에 대해 내가 넣은 가치가 큰지 안 넣은 가치가 큰지 비교하여 방정식 f[i][v...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
