CodeForces - 862B Mahmoud and Ehab and the bipartiteness(dfs)

11083 단어 codeforces
제목: 고리가 형성되지 않은 상황에서 몇 개의 변을 연결할 수 있는지 2분도를 제시한다.
제목: 이분도 염색을 두 부분, 홀수와 짝수로 나눈다.홀수의 점 수량은 a이고, 짝수의 점 수량은 b이다.그럼 이 2분도는 총 ab개의 테두리를 연결할 수 있습니다.제목은 n-1변을 연결했고 모든 것은 ab-(n-1)=a*b-n+1을 연결할 수 있습니다.
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define F first
#define S second
#define ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "
"
#define lowbit(x) ((x)&-(x))
typedef pair<int,int> PII;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int dis[][2]={{0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};
const int MOD=1e9+7;
const int N=1e5+10;
vector<int> g[N];
ll a,b;
void dfs(int u,int v,int w){
    if(w==1) a++;
    else b++;
    for(int i=0;i<g[v].size();i++){
        if(u==g[v][i]) continue;
        dfs(v,g[v][i],1-w);
    }
}

int main(){
    //IOS;
    int n;
    cin>>n;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    a=b=0;
    dfs(0,1,0);
    cout<<a*b-n+1<<endl;
    return 0;
}
Codeforces Round #627 (Div. 3) E&F
JS 구현 페이지 등 높 음

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage