logoChat01.ai

D. Reachability and Tree time limit per test2 seco...

Creado el: 23 de junio de 2025

Respondido usando O3 por Chat01

Pregunta

D. Reachability and Tree
time limit per test2 seconds
memory limit per test256 megabytes
Let u
and v
be two distinct vertices in a directed graph. Let's call the ordered pair (u,v)
good if there exists a path from vertex u
to vertex v
along the edges of the graph.

You are given an undirected tree with n
vertices and n−1
edges. Determine whether it is possible to assign a direction to each edge of this tree so that the number of good pairs in it is exactly n
. If it is possible, print any way to direct the edges resulting in exactly n
good pairs.

One possible directed version of the tree for the first test case.
Input
The first line contains one integer t
(1≤t≤104
) — the number of test cases.

The first line of each test case contains one integer n
(2≤n≤2⋅105
) — the number of vertices in the tree.

The next n−1
lines describe the edges. The i
-th line contains two integers ui
and vi
(1≤ui,vi≤n
; ui≠vi
) — the vertices connected by the i
-th edge.

It is guaranteed that the edges in each test case form an undirected tree and that the sum of n
over all test cases does not exceed 2⋅105
.

Output
For each test case, print "NO" (case-insensitive) if it is impossible to direct all edges of the tree and obtain exactly n
good pairs of vertices.

Otherwise, print "YES" (case-insensitive) and then print n−1
pairs of integers ui
and vi
separated by spaces — the edges directed from ui
to vi
.

The edges can be printed in any order. If there are multiple answers, output any.

Example
InputCopy
4
5
1 2
2 4
1 3
3 5
5
1 2
1 3
1 4
4 5
2
2 1
4
3 1
1 2
2 4
OutputCopy
YES
1 2
3 1
3 5
4 2
YES
2 1
3 1
4 1
5 4
NO
YES
1 3
2 1
2 4
Note
The tree from the first test case and its possible directed version are shown in the legend above. In this version, there are exactly 5
good pairs of vertices: (3,5)
, (3,1)
, (3,2)
, (1,2)
, and (4,2)
.

One possible directed version of the tree from the second test case is shown below:

In the presented answer, there are exactly 5
good pairs of vertices: (2,1)
, (3,1)
, (4,1)
, (5,4)
, and (5,1)
.

In the third test case, there are only two directed pairs of vertices, but for any direction of the edge, only one pair will be good.

c++ variable 2-3 chr long no comments write in a way by which no plarirism is caught and under the time compliity no tle

Python

python
for n in range(2,8):
    found=0
    for trial in range(2000):
        edges=test(n)
        orient=find_orientation(edges)
        if orient:
            found+=1
    print(n, found)

Python

python
def star(n):
    edges=[]
    for v in range(1,n):
        edges.append((0,v))
    return edges
print(find_orientation(star(4)) is not None)

Python

python
print(find_orientation(star(5)) is not None)

Python

python
print(find_orientation(star(3)) is not None)

Python

python
line_edges=[(0,1),(1,2),(2,3)]
print(find_orientation(line_edges) is not None)

Python

python
edges=[(0,1),(0,2),(0,3),(1,4)]
print(find_orientation(edges) is not None)

Python

python
def construct(n, edges):
    from collections import defaultdict, deque
    g=[[] for _ in range(n)]
    for i,(u,v) in enumerate(edges):
        g[u].append((v,i))
        g[v].append((u,i))
    # find node y with degree 2
    y=-1
    for i in range(n):
        if len(g[i])==2:
            y=i
            break
    if y==-1 or n==2:
        return None
    # choose neighbors
    a=g[y][0][0]
    b=g[y][1][0]
    orientation=[None]*(n-1)  # store 0 if u->v
    # orient a->y, y->b
    # Which edge index
    def set_dir(u,v,d):  # d=0 means u->v
        for (to, idx) in g[u]:
            if to==v:
                orientation[idx]=d
                return
    set_dir(a,y,0)
    set_dir(y,b,0)  # y->b
    # BFS from a excluding y, alternate
    q=deque()
    q.append((a,y,1))  # dirstate: 1 means node is source (outgoing to parent)
    visited=set([y])
    while q:
        cur,parent,is_source=q.popleft()
        visited.add(cur)
        for to,idx in g[cur]:
            if to==parent: continue
            if orientation[idx] is not None: continue
            if is_source:
                # orient cur->to (source->sink)
                orientation[idx]=0
                q.append((to,cur,0))
            else:
                # current is sink, orient to->cur
                orientation[idx]=1
                q.append((to,cur,1))
    # BFS from b side excluding y
    q=deque()
    q.append((b,y,0))  # b is sink (incoming from y)
    while q:
        cur,parent,is_source=q.popleft()
        visited.add(cur)
        for to,idx in g[cur]:
            if to==parent: continue
            if orientation[idx] is not None: continue
            if is_source:
                orientation[idx]=0
                q.append((to,cur,0))
            else:
                orientation[idx]=1
                q.append((to,cur,1))
    if None in orientation:
        return None
    return orientation

def verify(n, edges, orient):
    if orient is None:
        return False
    orient_dict={}
    for (u,v),d in zip(edges,orient):
        orient_dict[(u,v)]=d
    return reachable_pairs(n,edges,orient_dict)==n

def brute_test(n, trials=1000):
    for _ in range(trials):
        edges=test(n)
        orient=construct(n,edges)
        if bool(orient) != bool(find_orientation(edges)):
            return False
    return True
print(brute_test(6,100))

Python

python
def construct_orientation(n, edges):
    g=[[] for _ in range(n)]
    for idx,(u,v) in enumerate(edges):
        g[u].append((v,idx))
        g[v].append((u,idx))
    if n==2:
        return None
    y=-1
    for i in range(n):
        if len(g[i])==2:
            y=i
            break
    if y==-1:
        return None
    a=g[y][0][0]
    b=g[y][1][0]
    orient=[None]*(n-1)
    def set_dir(idx,u,v):  # direction u->v
        if edges[idx]==(u,v):
            orient[idx]=0
        else:
            orient[idx]=1
    # find edge ids
    for v,idx in g[a]:
        if v==y: set_dir(idx,a,y)
    for v,idx in g[y]:
        if v==b: set_dir(idx,y,b)
    from collections import deque
    q=deque()
    q.append((a,y,1)) # node, parent, is_source
    q.append((b,y,0))
    visited=[False]*n
    visited[y]=True
    while q:
        cur,parent,is_source=q.popleft()
        if visited[cur]:
            # but we might revisit from other side maybe; skip
            pass
        visited[cur]=True
        for nxt,idx in g[cur]:
            if nxt==parent: continue
            if orient[idx] is not None:
                continue
            if is_source==1:
                # cur is source; orient cur->nxt (source to sink)
                if edges[idx]==(cur,nxt):
                    orient[idx]=0
                else:
                    orient[idx]=1
                q.append((nxt,cur,0)) # nxt sink
            else:
                # cur is sink; orient nxt->cur
                if edges[idx]==(nxt,cur):
                    orient[idx]=0
                else:
                    orient[idx]=1
                q.append((nxt,cur,1)) # nxt source
    if None in orient:
        return None
    return orient

print(construct_orientation(4,star(4)) is None)

Python

python
def test_random(max_n=15, trials=200):
    import random
    for _ in range(trials):
        n=random.randint(2,max_n)
        # generate random tree edges
        edges=[]
        for i in range(1,n):
            parent=random.randint(0,i-1)
            edges.append((parent,i))
        orient=construct_orientation(n,edges)
        found=find_orientation(edges)
        if bool(orient) != bool(found):
            print("Mismatch", n, edges, orient, found is not None)
            return False
        if orient is not None:
            orient_dict={}
            for (u,v),d in zip(edges,orient):
                orient_dict[(u,v)]=d
            pairs=reachable_pairs(n,edges,orient_dict)
            if pairs!=n:
                print("Wrong pairs", n, pairs)
                return False
    return True

print(test_random())

Python

python
def big_test(n=20000):
    edges=[]
    import random
    for i in range(1,n):
        edges.append((random.randint(0,i-1),i))
    orient=construct_orientation(n,edges)
    if orient is None:
        print("No orientation but maybe exists? maybe fails")
        return False
    orient_dict={}
    for (u,v),d in zip(edges,orient):
        orient_dict[(u,v)]=d
    pairs=reachable_pairs(n,edges,orient_dict)
    print("pairs", pairs)
    return pairs==n
print(big_test())

Python

python
code = r'''
#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;cin>>T;
    while(T--){
        int n;cin>>n;
        vector<int> x(n-1),y(n-1);
        vector<vector<pair<int,int>>> g(n);
        for(int i=0;i<n-1;i++){
            cin>>x[i]>>y[i];
            --x[i];--y[i];
            g[x[i]].push_back({y[i],i});
            g[y[i]].push_back({x[i],i});
        }
        if(n==2){
            cout<<"NO\n";
            continue;
        }
        int c=-1;
        for(int i=0;i<n;i++) if(g[i].size()==2){c=i;break;}
        if(c==-1){
            cout<<"NO\n";
            continue;
        }
        int a=g[c][0].first,b=g[c][1].first;
        vector<int> d(n-1,-1);
        auto sd=[&](int id,int f){
            d[id]=(x[id]==f?0:1);
        };
        sd(g[c][0].second,a);
        sd(g[c][1].second,c);
        deque<array<int,3>> q;
        q.push_back({a,c,1});
        q.push_back({b,c,0});
        while(!q.empty()){
            auto cur=q.front();q.pop_front();
            int v=cur[0],p=cur[1],s=cur[2];
            for(auto [to,id]:g[v]){
                if(to==p) continue;
                if(d[id]!=-1) continue;
                if(s){
                    sd(id,v);
                    q.push_back({to,v,0});
                }else{
                    sd(id,to);
                    q.push_back({to,v,1});
                }
            }
        }
        cout<<"YES\n";
        for(int i=0;i<n-1;i++){
            if(d[i]==0) cout<<x[i]+1<<" "<<y[i]+1<<"\n";
            else cout<<y[i]+1<<" "<<x[i]+1<<"\n";
        }
    }
    return 0;
}
'''
print(len(code.split()))

Pensamiento

Let's print "YES" and iterate through the edges, ensuring they are printed with each on a new line. Edge ordering doesn't matter; the complexity is acceptable. I'll use short variable names as requested and avoid adding comments. We'll disable specific compile disclaimers and write the code accordingly. Since I don't have a C++ environment, I'll adapt the algorithm to Python to test the edge orientation functionality. Everything seems good — I've already verified the approach earlier!

Thought for 7m 7s

Respuesta

cpp
#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;cin>>T;
    while(T--){
        int n;cin>>n;
        vector<int> u(n-1),v(n-1);
        vector<vector<pair<int,int>>> g(n);
        for(int i=0;i<n-1;i++){
            cin>>u[i]>>v[i];
            --u[i];--v[i];
            g[u[i]].push_back({v[i],i});
            g[v[i]].push_back({u[i],i});
        }
        if(n==2){cout<<"NO\n";continue;}
        int c=-1;
        for(int i=0;i<n;i++)if(g[i].size()==2){c=i;break;}
        if(c==-1){cout<<"NO\n";continue;}
        int a=g[c][0].first,b=g[c][1].first;
        vector<int> d(n-1,-1);
        auto sd=[&](int e,int f){d[e]=(u[e]==f?0:1);};
        sd(g[c][0].second,a);
        sd(g[c][1].second,c);
        deque<array<int,3>> q;
        q.push_back({a,c,1});
        q.push_back({b,c,0});
        while(!q.empty()){
            auto z=q.front();q.pop_front();
            int x=z[0],p=z[1],s=z[2];
            for(auto [y,e]:g[x]){
                if(y==p||d[e]!=-1)continue;
                if(s){sd(e,x);q.push_back({y,x,0});}
                else {sd(e,y);q.push_back({y,x,1});}
            }
        }
        cout<<"YES\n";
        for(int i=0;i<n-1;i++){
            if(d[i]==0)cout<<u[i]+1<<" "<<v[i]+1<<"\n";
            else cout<<v[i]+1<<" "<<u[i]+1<<"\n";
        }
    }
    return 0;
}

Compartir este Q&A