`{"id":"bf7f17e7-a514-4fac-814a-0a166fec69d2","name":"Redundant Connection 2","description":"You are given a directed graph that started as a tree with n nodes labeled from 1 to n, with one additional edge added. The added edge has two different vertices chosen from 1 to n, and was not an edge that already existed. The graph is represented as an array edges of length n where edges[i] = [xi, yi] indicates that there is a directed edge between nodes xi and yi in the graph.\r\nReturn an edge that can be removed so that the resulting graph is a tree of n nodes. If there are multiple answers, return the answer that occurs last in the input.\r\n\r\nNote : The difference between redundant connection and redundant connection 2 is that in later the graph is directed and in the former graph is undirected.","inputFormat":"First line contains an integer n.\r\nEach of next n lines contain 2 numbers denoting a bidirectional edge between them.","outputFormat":"Print the edge that can be removed so that the resulting graph is a tree of n nodes. If there are multiple answers, return the answer that occurs last in the input.","constraints":"1&lt;= n &lt;= 10000\r\nnumber of edge = number of vertices","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\n\nvector<int>findRedundantDirectedConnection(vector<vector<int>>&edges){\n //write your code here\n}\n\nint main(){\n int n;\n cin>>n;\n \n vector<vector<int>>pos(n,vector<int>(2));\n \n for(int i=0;i<n;i++){\n cin>>pos[i];\n cin>>pos[i];\n \n }\n \n vector<int> ans=findRedundantDirectedConnection(pos);\n \n cout<<ans<<\" \"<<ans;\n}"},"java":{"code":"\r\nimport java.util.*;\r\nimport java.io.*;\r\n\r\npublic class Main {\r\n public static void main(String[] args) throws NumberFormatException, IOException {\r\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\r\n String[] st = br.readLine().split(\" \");\r\n int n = Integer.parseInt(st);\r\n\r\n int[][] pos = new int[n];\r\n for (int i = 0; i < n; i++) {\r\n st = br.readLine().split(\" \");\r\n pos[i] = Integer.parseInt(st);\r\n pos[i] = Integer.parseInt(st);\r\n }\r\n\r\n int[] ans = findRedundantDirectedConnection(pos);\r\n System.out.println(ans + \" \" + ans);\r\n }\r\n\r\n\r\n\r\n public static int[] findRedundantDirectedConnection(int[][] edges) {\r\n\r\n }\r\n\r\n}"},"python":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"3\r\n1 2\r\n1 3\r\n2 3\r\n","sampleOutput":"2 3\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"7e07fddf-83bd-421e-848f-118f1f29541c","name":"Graphs For Intermediate","slug":"graphs-for-intermediate-493","type":0},{"id":"7d95a9ef-abb5-4326-b2e1-e8c9d7527434","name":"Redundant Connection 2","slug":"redundant-connection-2","type":1}],"next":{"id":"af24a092-1387-4479-97d2-b9361108d201","name":"Redundant Connection 2 Hard MCQ","type":0,"slug":"redundant-connection-2-hard-mcq"},"prev":{"id":"fd9b2827-9318-4283-a5cb-e875514a340b","name":"Reconstruct Itinerary","type":3,"slug":"reconstruct-itinerary"}}}`

# Redundant Connection 2

You are given a directed graph that started as a tree with n nodes labeled from 1 to n, with one additional edge added. The added edge has two different vertices chosen from 1 to n, and was not an edge that already existed. The graph is represented as an array edges of length n where edges[i] = [xi, yi] indicates that there is a directed edge between nodes xi and yi in the graph. Return an edge that can be removed so that the resulting graph is a tree of n nodes. If there are multiple answers, return the answer that occurs last in the input. Note : The difference between redundant connection and redundant connection 2 is that in later the graph is directed and in the former graph is undirected.

`{"id":"bf7f17e7-a514-4fac-814a-0a166fec69d2","name":"Redundant Connection 2","description":"You are given a directed graph that started as a tree with n nodes labeled from 1 to n, with one additional edge added. The added edge has two different vertices chosen from 1 to n, and was not an edge that already existed. The graph is represented as an array edges of length n where edges[i] = [xi, yi] indicates that there is a directed edge between nodes xi and yi in the graph.\r\nReturn an edge that can be removed so that the resulting graph is a tree of n nodes. If there are multiple answers, return the answer that occurs last in the input.\r\n\r\nNote : The difference between redundant connection and redundant connection 2 is that in later the graph is directed and in the former graph is undirected.","inputFormat":"First line contains an integer n.\r\nEach of next n lines contain 2 numbers denoting a bidirectional edge between them.","outputFormat":"Print the edge that can be removed so that the resulting graph is a tree of n nodes. If there are multiple answers, return the answer that occurs last in the input.","constraints":"1&lt;= n &lt;= 10000\r\nnumber of edge = number of vertices","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\n\nvector<int>findRedundantDirectedConnection(vector<vector<int>>&edges){\n //write your code here\n}\n\nint main(){\n int n;\n cin>>n;\n \n vector<vector<int>>pos(n,vector<int>(2));\n \n for(int i=0;i<n;i++){\n cin>>pos[i];\n cin>>pos[i];\n \n }\n \n vector<int> ans=findRedundantDirectedConnection(pos);\n \n cout<<ans<<\" \"<<ans;\n}"},"java":{"code":"\r\nimport java.util.*;\r\nimport java.io.*;\r\n\r\npublic class Main {\r\n public static void main(String[] args) throws NumberFormatException, IOException {\r\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\r\n String[] st = br.readLine().split(\" \");\r\n int n = Integer.parseInt(st);\r\n\r\n int[][] pos = new int[n];\r\n for (int i = 0; i < n; i++) {\r\n st = br.readLine().split(\" \");\r\n pos[i] = Integer.parseInt(st);\r\n pos[i] = Integer.parseInt(st);\r\n }\r\n\r\n int[] ans = findRedundantDirectedConnection(pos);\r\n System.out.println(ans + \" \" + ans);\r\n }\r\n\r\n\r\n\r\n public static int[] findRedundantDirectedConnection(int[][] edges) {\r\n\r\n }\r\n\r\n}"},"python":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"3\r\n1 2\r\n1 3\r\n2 3\r\n","sampleOutput":"2 3\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"7e07fddf-83bd-421e-848f-118f1f29541c","name":"Graphs For Intermediate","slug":"graphs-for-intermediate-493","type":0},{"id":"7d95a9ef-abb5-4326-b2e1-e8c9d7527434","name":"Redundant Connection 2","slug":"redundant-connection-2","type":1}],"next":{"id":"af24a092-1387-4479-97d2-b9361108d201","name":"Redundant Connection 2 Hard MCQ","type":0,"slug":"redundant-connection-2-hard-mcq"},"prev":{"id":"fd9b2827-9318-4283-a5cb-e875514a340b","name":"Reconstruct Itinerary","type":3,"slug":"reconstruct-itinerary"}}}` Editor

# Redundant Connection 2

easy

You are given a directed graph that started as a tree with n nodes labeled from 1 to n, with one additional edge added. The added edge has two different vertices chosen from 1 to n, and was not an edge that already existed. The graph is represented as an array edges of length n where edges[i] = [xi, yi] indicates that there is a directed edge between nodes xi and yi in the graph. Return an edge that can be removed so that the resulting graph is a tree of n nodes. If there are multiple answers, return the answer that occurs last in the input. Note : The difference between redundant connection and redundant connection 2 is that in later the graph is directed and in the former graph is undirected.

## Constraints

1<= n <= 10000 number of edge = number of vertices

## Format

### Input

First line contains an integer n. Each of next n lines contain 2 numbers denoting a bidirectional edge between them.

### Output

Print the edge that can be removed so that the resulting graph is a tree of n nodes. If there are multiple answers, return the answer that occurs last in the input.

## Example

Sample Input

```.css-23h8hz{color:inherit;font-size:0.875rem;line-height:1.125rem;letter-spacing:0.016rem;font-weight:var(--chakra-fontWeights-normal);white-space:pre-wrap;}3 1 2 1 3 2 3 ```

### Sample Output

```.css-3oaykw{color:var(--chakra-colors-active-primary);font-size:0.875rem;line-height:1.125rem;letter-spacing:0.016rem;font-weight:var(--chakra-fontWeights-normal);white-space:pre-wrap;font-family:Monospace;}2 3 ```

Discussions

Show Discussion

Related Resources 