Un graf conex cu N noduri și M muchii poate fi privit ca o clepsidră cu centrul în nodul X, 1 ≤ X ≤ N, dacă putem împărți toate nodurile, mai puțin nodul X, în două submulțimi nevide astfel încât orice drum de la un nod dintr-o mulțime la un nod din cealaltă mulțime trece prin nodul X. Voi trebuie să determinați numărul de moduri distincte în care putem privi graful ca o clepsidră pentru fiecare din cele N noduri alese drept centru, modulo 666013. Două moduri se consideră distincte dacă cele două submulțimi aferente sunt diferite. Ordinea submulțimilor într-un mod este relevantă, dar ordinea nodurilor în cadrul unei mulțimi nu este. Spre exemplu, soluțiile ({1,2,3}, {4,5}) şi ({4,5}, {1,2,3}) sunt distincte, dar soluţiile ({4,5}, {1,2,3}) şi ({4,5}, {1,3,2}) nu sunt distincte.

Date de intrare

Fișierul de intrare clepsidra.in conține pe prima linie două numere naturale, N și M, reprezentând numărul de noduri, respectiv numărul de muchii din graf. Pe următoarele M linii se vor afla câte două numere naturale separate prin câte un spaţiu, reprezentând câte o muchie.

Date de ieșire

Fișierul de ieșire clepsidra.out va conține N linii. A i-a linie, 1 ≤ i ≤ N, va conține numărul de moduri în care putem privi graful ca o clepsidră cu centrul în nodul i, modulo 666013.

Restricții și precizări

2 ≤ N ≤ 200 002
1 ≤ M ≤ 250 002
Pentru 40% din teste avem restricţiile 2 ≤ N ≤ 1002 și 1 ≤ M ≤ 1502.
Atentie! Graful este conex.

Exemplu

clepsidra.in

clepsidra.out

Explicație

Pentru nodul cu indicele 3, soluţiile sunt: ({2}, {1,4,5,6}) și ({1,4,5,6}, {2})
Pentru nodul cu indicele 5, soluţiile sunt: ({6}, {1,2,3,4}) și ({1,2,3,4},{6})

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Clepsidra:

#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

#define MAXN 300010
#define MOD 666013

vector<int> G[MAXN];
int D[MAXN], Lv[MAXN], Ans[MAXN], Power[MAXN];
bool Ok[MAXN];
int N, M;

void df(int nod, int tata)
{
    Ok[nod] = true;
    Lv[nod] = Lv[tata] + 1;
    int nr = 1;
    if (nod == 1) nr = 0;
    D[nod] = Lv[nod];
    for (vector<int>::iterator it = G[nod].begin(); it != G[nod].end(); ++it){
        int nod2 = *it;
        if (nod2 == tata) continue;
        if (Ok[nod2]) {
            D[nod] = min(D[nod], Lv[nod2]);
            continue;
        }
        df(nod2, nod);
        if (D[nod2] >= Lv[nod])
            ++nr;
        D[nod] = min(D[nod2], D[nod]);
    }
    Ans[nod] = Power[nr];
}
int main()
{
    freopen("clepsidra.in","r",stdin);
    freopen("clepsidra.out","w",stdout);
    
    scanf("%d %d", &N, &M);
    for (int i = 1; i <= M; ++i){
        int x, y;
        scanf("%d %d", &x, &y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    
    Power[0] = 1; 
    for (int i = 1; i <= N; ++i)
        Power[i] = (Power[i - 1] * 2) % MOD;
    for (int i = 1; i <= N; ++i)
        Power[i] = (Power[i] + MOD - 2) % MOD;
    
    df(1, 0);
    
    for (int i = 1; i <= N; ++i)
        printf("%d
", Ans[i]);
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1118 Clepsidra

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1118 Clepsidra de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1118 Clepsidra