#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
#include <map>
#include <queue>
using namespace std;
#define POSITIVE_INFINITY (1<<30)
#define NEGATIVE_INFINITY (-1*(1<<30))
class Graf{
public:
struct edge{
int from;
int to;
int cost;
};
Graf(int nrNodes, int nrEdges, bool isOriented, vector<vector<int>> &adjacencyList);
Graf(int nrNodes, int nrEdges, bool isOriented, vector<vector<int>> &adjacencyList, bool isCostGraph, vector<edge> &edges);
Graf(int nrNodes, bool isOriented, vector<vector<int>> costMatrix);
void test();
vector<int> bfs(int start);
int dfs();
vector<vector<int>> biconnectedComponents();
vector<int> topSort();
vector<int> strongConnectedComponents();
vector<int> eulerianCircuit();
vector<int> dijkstra(int start);
vector<int> bellmanFord(int start);
int darb();
vector<vector<int>> royFloyd();
int getCost(int from, int to);
private:
//date membre
int m_nrNodes;
int m_nrEdges;
bool m_isOriented;
bool m_isCostGraph;
vector<vector<int>> m_adjacencyList;
vector<edge> m_edges;
vector<vector<int>> m_costMatrix;
//functii ajutatoare
void dfsRec(int start, vector<bool> &visited);
void biconnectedComponentsDFS(int u, vector<int> &disc, vector<int> &low, vector<edge> &st, vector<int> &parent, vector<vector<int>> &result);
int dfsTop(int idx, int crtNode, vector<bool> &visited, vector<int> &result);
void dfsStrConComp(int i, vector<int> &ids, vector<int> &low, vector<bool> &isOnStack, vector<int> &stack, int &idx);
int min(int a, int b);
void euler(int node, vector<int> &result, vector<vector<int>> &adjencyList);
pair<int, int> bfsDarb(int start);
};
Graf::Graf(int nrNodes, int nrEdges, bool isOriented, vector<vector<int>> &adjacencyList) {
m_nrNodes = nrNodes;
m_nrEdges = nrEdges;
m_isOriented = isOriented;
m_isCostGraph = false;
edge crtEdge;
m_adjacencyList.resize(nrNodes + 1);
for(int i = 1; i <= nrNodes; i++){
for(int j = 0; j < adjacencyList[i].size(); j++){
m_adjacencyList[i].push_back(adjacencyList[i][j]);
if(!isOriented){
m_adjacencyList[adjacencyList[i][j]].push_back(i);
}
crtEdge.from = i;
crtEdge.to = adjacencyList[i][j];
crtEdge.cost = 1;
m_edges.push_back(crtEdge);
}
}
}
void Graf::test(){
cout << m_nrNodes << " " << m_nrEdges << '\n';
for(int i = 1; i <= m_nrNodes; i++){
cout<<i<<": ";
for(int j : m_adjacencyList[i]){
cout<<j<<", ";
}
cout<<'\n';
}
}
Graf::Graf(int nrNodes, int nrEdges, bool isOriented, vector<vector<int>> &adjacencyList, bool isCostGraph, vector<edge> &edges) {
m_nrNodes = nrNodes;
m_nrEdges = nrEdges;
m_isOriented = isOriented;
m_isCostGraph = isCostGraph;
m_adjacencyList.resize(nrNodes + 1);
for(int i = 1; i <= nrNodes; i++){
for(int j = 0; j < adjacencyList[i].size(); j++){
m_adjacencyList[i].push_back(adjacencyList[i][j]);
if(!isOriented){
m_adjacencyList[adjacencyList[i][j]].push_back(i);
}
}
}
for(int i = 0; i < nrEdges; i++){
edge crtEdge{edges[i].from, edges[i].to, edges[i].cost};
m_edges.push_back(crtEdge);
}
}
vector<int> Graf::bfs(int start) {
vector<int> result;
vector<bool> visited;
for(int i=1; i<=m_nrNodes+1; i++){
visited.push_back(false);
}
deque<int> dq;
vector<int> prev;
for(int i=1; i<=m_nrNodes+1; i++){
prev.push_back(0);
}
dq.push_back(start);
visited[start] = true;
while(!dq.empty()){
int crt = dq.front();
dq.pop_front();
for(int i : m_adjacencyList[crt]){
if(!visited[i]){
dq.push_back(i);
visited[i] = true;
prev[i] = crt;
}
}
}
for(int f = 1; f <= m_nrNodes; f++){
int steps = 0;
int lastVisited;
for(int i = f; i != 0; i = prev[i]){
steps++;
lastVisited = i;
}
if(lastVisited != start) { result.push_back(-1); }
else { result.push_back(steps - 1); }
}
return result;
}
int Graf::dfs() {
vector<bool> visited;
for(int i = 0; i <= m_nrNodes; i++){
visited.push_back(false);
}
int nrConexComponents = 0;
for(int i = 1; i <= m_nrNodes; i++){
if(!visited[i]){
nrConexComponents++;
dfsRec(i, visited);
}
}
return nrConexComponents;
}
void Graf::dfsRec(int start, vector<bool> &visited) {
visited[start] = true;
for(auto i : m_adjacencyList[start]){
if(!visited[i]){
dfsRec(i, visited);
}
}
}
vector<vector<int>> Graf::biconnectedComponents() {
vector<int> disc, low, parent;
vector<edge> st;
// Initialize disc and low, and parent arrays
for (int i = 0; i <= m_nrNodes; i++) {
disc.push_back(-1);
low.push_back(-1);
parent.push_back(-1);
}
vector<vector<int>> result;
for (int i = 1; i <= m_nrNodes; i++) {
if (disc[i] == -1)
biconnectedComponentsDFS(i, disc, low, st, parent, result);
vector<int> component;
int j = 0;
// If stack is not empty, pop all edges from stack
while (!st.empty()) {
j = 1;
bool isFrom = false, isTo = false;
for(int node : component){
if(node == st.back().to){
isTo = true;
}
if(node == st.back().from){
isFrom = true;
}
}
if(!isFrom && !isTo){
component.push_back(st.back().to);
}
else if(isFrom && !isTo){
component.push_back(st.back().to);
}
else if(!isFrom && isTo){
component.push_back(st.back().from);
}
st.pop_back();
}
if (j == 1) {
result.push_back(component);
}
}
return result;
}
void Graf::biconnectedComponentsDFS(int u, vector<int> &disc, vector<int> &low, vector<edge> &st, vector<int> &parent, vector<vector<int>> &result) {
static int time = 0;
// Initialize discovery time and low value
disc[u] = low[u] = ++time;
int children = 0;
// Go through all vertices adjacent to this
for (auto v : m_adjacencyList[u]) {
// If v is not visited yet, then recur for it
if (disc[v] == -1) {
children++;
parent[v] = u;
// store the edge in stack
edge crtEdge{u, v, 0};
st.push_back(crtEdge);
biconnectedComponentsDFS(v, disc, low, st, parent, result);
// Check if the subtree rooted with 'v' has a
// connection to one of the ancestors of 'u'
if(low[u] > low[v]) low[u] = low[v];
vector<int> component;
// If u is an articulation point,
// pop all edges from stack till u -- v
if ((disc[u] == 1 && children > 1) || (disc[u] > 1 && low[v] >= disc[u])) {
while (st.back().from != u || st.back().to != v) {
bool isFrom = false, isTo = false;
for(int node : component){
if(node == st.back().to){
isTo = true;
}
if(node == st.back().from){
isFrom = true;
}
}
if(!isFrom && !isTo){
component.push_back(st.back().to);
}
else if(isFrom && !isTo){
component.push_back(st.back().to);
}
else if(!isFrom && isTo){
component.push_back(st.back().from);
}
st.pop_back();
}
bool isFrom = false, isTo = false;
for(int node : component){
if(node == st.back().to){
isTo = true;
}
if(node == st.back().from){
isFrom = true;
}
}
if(!isFrom && !isTo){
component.push_back(st.back().to);
}
else if(isFrom && !isTo){
component.push_back(st.back().to);
}
else if(!isFrom && isTo){
component.push_back(st.back().from);
}
st.pop_back();
result.push_back(component);
}
}
else if (v != parent[u]) {
if(low[u] > low[v]) low[u] = low[v];
if (disc[v] < disc[u]) {
edge crtEdge{u, v, 0};
st.push_back(crtEdge);
}
}
}
}
vector<int> Graf::topSort() {
vector<bool> visited;
for(int i = 0; i <= m_nrNodes; i++){
visited.push_back(false);
}
vector<int> result;
result.resize(m_nrNodes);
int idx = m_nrNodes - 1;
for(int i = 1; i <= m_nrNodes; i++){
if(!visited[i]){
idx = dfsTop(idx, i, visited, result);
}
}
return result;
}
int Graf::dfsTop(int idx, int crtNode, vector<bool> &visited, vector<int> &result) {
visited[crtNode] = true;
for(int i : m_adjacencyList[crtNode]){
if(!visited[i]){
idx = dfsTop(idx, i, visited, result);
}
}
result[idx] = crtNode;
return idx - 1;
}
vector<int> Graf::strongConnectedComponents() {
int idx = 0;
vector<int> ids, low;
vector<bool> isOnStack;
vector<int> stack;
low.resize(m_nrNodes + 1);
isOnStack.resize(m_nrNodes + 1);
for(int i = 0; i <= m_nrNodes; i++){
ids.push_back(-1);
}
for(int i = 1; i <= m_nrNodes; i++){
if(ids[i] == -1){
dfsStrConComp(i, ids, low, isOnStack, stack, idx);
}
}
return low;
}
void Graf::dfsStrConComp(int i, vector<int> &ids, vector<int> &low, vector<bool> &isOnStack, vector<int> &stack, int &idx) {
stack.push_back(i);
isOnStack[i] = true;
ids[i] = low[i] = idx++;
for(auto to : m_adjacencyList[i]){
if(ids[to] == -1) dfsStrConComp(to, ids, low, isOnStack, stack, idx);
if(isOnStack[to]) low[i] = min(low[i], low[to]);
}
if(ids[i] == low[i]){
while(!stack.empty()){
auto node = stack.back();
isOnStack[node] = false;
low[node] = ids[i];
if(node == i) break;
stack.pop_back();
}
// for(auto node = stack.back(); !stack.empty(); stack.pop_back()){
// isOnStack[node] = false;
// low[node] = ids[i];
// if(node == i) break;
// node = stack.back();
// }
}
}
int Graf::min(int a, int b) {
if(a < b) return a;
return b;
}
vector<int> Graf::eulerianCircuit() {
vector<int> result;
for (int i = 1; i <= m_nrNodes; i++) {
if (m_adjacencyList[i].size() % 2) {
result.push_back(-1);
return result;
}
}//daca gasim vreun nod cu grad impar atunci nu avem ciclu Euler
vector<vector<int>> adjacencyListCopy = m_adjacencyList;
euler(1, result, adjacencyListCopy);
return result;
}
void Graf::euler(int node, vector<int> &result, vector<vector<int>> &adjencyList) {
while(!adjencyList[node].empty()){
int next = adjencyList[node].back();
adjencyList[node].pop_back();
for(auto i = adjencyList[next].begin(); i != adjencyList[next].end(); i++){
if(*i == node){
adjencyList[next].erase(i);
break;
}
}
euler(next, result, adjencyList);
}
result.push_back(node);
}
vector<int> Graf::dijkstra(int start) {
vector<int> dist;
vector<bool> visited;
for(int i = 0; i <= m_nrNodes; i++){
visited.push_back(false);
dist.push_back(1 << 30);
}
dist[start] = 0;
priority_queue<pair<int, int>> pq; // pq(dist, node)
pq.push(make_pair(0, start));
while(!pq.empty()){
pair<int, int> pair = pq.top(); //make_pair(minValue, index)
cout<<pair.first<<" "<<pair.second<<'\n';
visited[pair.second] = true;
if(dist[pair.second] < pair.first) continue;
for(int next : m_adjacencyList[pair.second]){
if(visited[next]) continue;
int newDist = dist[pair.second] + getCost(pair.second, next);
if(newDist < dist[next]){
dist[next] = newDist;
pq.push(make_pair(newDist, next));
//cout<<newDist<<" "<<next<<'\n';
}
}
pq.pop();
}
return dist;
}
int Graf::getCost(int from, int to) {
if(from == to) return 0;
for(int i = 0; i < m_nrEdges; i++){
if(m_edges[i].from == from && m_edges[i].to == to){
return m_edges[i].cost;
}
}
return -1;
}
vector<int> Graf::bellmanFord(int start) {
vector<int> dist;
for(int i = 0; i <= m_nrNodes + 1; i++){
dist.push_back(POSITIVE_INFINITY);
}
dist[start] = 0;
for(int i = 0; i < m_nrNodes - 1; i++){
for(edge edge : m_edges){
if(dist[edge.from] + edge.cost < dist[edge.to]){
dist[edge.to] = dist[edge.from] + edge.cost;
}
}
}
//run again to find negative cycles
for(int i = 0; i < m_nrNodes - 1; i++){
for(edge edge : m_edges){
if(dist[edge.from] + edge.cost < dist[edge.to]){
dist[edge.to] = NEGATIVE_INFINITY;
dist[0] = NEGATIVE_INFINITY;
}
}
}
return dist;
}
pair<int, int> Graf::bfsDarb(int start) {//returns (lastVisited, val)
vector<bool> visited;
for(int i=1; i<=m_nrNodes+1; i++){
visited.push_back(false);
}
deque<int> dq;
vector<int> prev;
for(int i=1; i<=m_nrNodes+1; i++){
prev.push_back(0);
}
dq.push_back(start);
visited[start] = true;
int lastVisited;
while(!dq.empty()){
int crt = dq.front();
dq.pop_front();
for(int i : m_adjacencyList[crt]){
if(!visited[i]){
dq.push_back(i);
visited[i] = true;
prev[i] = crt;
lastVisited = i;
}
}
}
int steps = 0;
for(int i = lastVisited; i != 0; i = prev[i]){
steps++;
}
return make_pair(lastVisited, steps);
}
int Graf::darb() {
pair<int, int> lastVisitedAndPathSize = bfsDarb(1);
int darb = bfsDarb(lastVisitedAndPathSize.first).second;
return darb;
}
Graf::Graf(int nrNodes, bool isOriented, vector<vector<int>> costMatrix) {
m_nrNodes = nrNodes;
m_isOriented = isOriented;
m_costMatrix.resize(nrNodes + 1);
m_adjacencyList.resize(nrNodes + 1);
m_nrEdges = 0;
m_isCostGraph = true;
for(int i = 1; i <= nrNodes; i++){
m_costMatrix[i].push_back(0);
for(int j = 1; j <= nrNodes; j++){
m_costMatrix[i].push_back(costMatrix[i][j]);
if(costMatrix[i][j]) {
edge crtEdge = {i, j, costMatrix[i][j]};
m_edges.push_back(crtEdge);
m_adjacencyList[i].push_back(j);
m_nrEdges += 1;
}
}
}
if(!isOriented){
m_nrEdges /= 2;
}
}
vector<vector<int>> Graf::royFloyd() {
vector<vector<int>> dist;
dist.resize(m_nrNodes + 1);
for(int i = 0; i <= m_nrNodes; i++){
for(int j = 0; j <= m_nrNodes; j++){
dist[i].push_back(POSITIVE_INFINITY);
}
}
for(int i = 1; i<= m_nrNodes; i++){
dist[i][i] = 0;
}
for(edge edge : m_edges){
dist[edge.from][edge.to] = edge.cost;
}
for(int k = 1; k <= m_nrNodes; k++){
for(int i = 1; i <= m_nrNodes; i++){
for(int j = 1; j <= m_nrNodes; j++){
if(dist[i][j] > dist[i][k] + dist[k][j]){
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
return dist;
}
void bfsInfoArena(){
ifstream fin("bfs.in");
ofstream fout("bfs.out");
int n, m, x, from, to;
vector<vector<int>> la;
fin>>n>>m>>x;
la.resize(n+1);
for(int i = 0; i < m; i++){
fin>>from>>to;
la[from].push_back(to);
}
Graf graf = Graf(n, m, true, la);
vector<int> res = graf.bfs(x);
for(int i : res){
fout<<i<<" ";
}
}
void dfsInfoArena(){
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int n, m, from, to;
vector<vector<int>> la;
fin>>n>>m;
la.resize(n+1);
for(int i = 0; i < m; i++){
fin>>from>>to;
la[from].push_back(to);
}
Graf graf = Graf(n, m, false, la);
fout<<graf.dfs();
}
void biconexInfoArena(){
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n, m, from, to;
vector<vector<int>> la;
fin>>n>>m;
la.resize(n+1);
for(int i = 0; i < m; i++){
fin>>from>>to;
la[from].push_back(to);
}
Graf graf = Graf(n, m, false, la);
vector<vector<int>> componenteBiconexe = graf.biconnectedComponents();
fout<<componenteBiconexe.size()<<'\n';
for(auto i: componenteBiconexe){
for(auto j : i){
fout<<j<<" ";
}
fout<<'\n';
}
}
void sortaretInfoArena(){
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
int n, m, from, to;
vector<vector<int>> la;
fin>>n>>m;
la.resize(n+1);
for(int i = 0; i < m; i++){
fin>>from>>to;
la[from].push_back(to);
}
Graf graf = Graf(n, m, true, la);
vector<int> sortare = graf.topSort();
for(auto i: sortare){
fout<<i<<" ";
}
}
void ctcInfoArena(){
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, from, to;
vector<vector<int>> la;
fin>>n>>m;
la.resize(n+1);
for(int i = 0; i < m; i++){
fin>>from>>to;
la[from].push_back(to);
}
Graf graf = Graf(n, m, true, la);
vector<int> rezultat = graf.strongConnectedComponents();
// for(auto i: rezultat){
// cout<<i<<" ";
// }
map<int, vector<int>> componente;
for(int i = 1; i <= n; i++){
componente[rezultat[i]].push_back(i);
}
fout<<componente.size()<<'\n';
for(auto comp : componente){
for(auto nod : comp.second){
fout<<nod<<" ";
}
fout<<'\n';
}
}
void dijkstraInfoArena(){
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int n, m, from, to, cost;
vector<vector<int>> la;
vector<Graf::edge> edges;
fin>>n>>m;
la.resize(n+1);
for(int i = 0; i < m; i++){
fin>>from>>to>>cost;
la[from].push_back(to);
Graf::edge crtEdge{from, to, cost};
edges.push_back(crtEdge);
}
Graf graf = Graf(n, m, true, la, true, edges);
vector<int> rezultat = graf.dijkstra(1);
for(int i = 2; i <= n; i++){
fout<<rezultat[i]<<" ";
}
//graf.test();
}
void cicluEulerianInfoArena(){
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
int n, m, from, to;
vector<vector<int>> la;
fin>>n>>m;
la.resize(n+1);
for(int i = 0; i < m; i++){
fin>>from>>to;
la[from].push_back(to);
}
Graf graf = Graf(n, m, false, la);
vector<int> rezultat = graf.eulerianCircuit();
for(auto i: rezultat){
fout<<i<<" ";
}
}
void bellmanFordInfoArena(){
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int n, m, from, to, cost;
vector<vector<int>> la;
vector<Graf::edge> edges;
fin>>n>>m;
la.resize(n+1);
for(int i = 0; i < m; i++){
fin>>from>>to>>cost;
la[from].push_back(to);
Graf::edge crtEdge{from, to, cost};
edges.push_back(crtEdge);
}
Graf graf = Graf(n, m, true, la, true, edges);
vector<int> rezultat = graf.bellmanFord(1);
if(rezultat[0] == NEGATIVE_INFINITY) fout<<"Ciclu negativ!";
else{
for(int i = 2; i <= n; i++){
fout<<rezultat[i]<<" ";
}
}
}
void darbInfoArena(){
ifstream fin("darb.in");
ofstream fout("darb.out");
int n, from, to;
vector<vector<int>> la;
fin>>n;
la.resize(n+1);
for(int i = 0; i < n-1; i++){
fin>>from>>to;
la[from].push_back(to);
}
Graf graf = Graf(n, n-1, false, la);
int res = graf.darb();
fout<<res;
}
void royfloydInfoArena(){
ifstream fin("royfloyd.in");
ofstream fout("royfloyd.out");
int n, cost;
vector<vector<int>> matriceCosturi;
fin>>n;
matriceCosturi.resize(n+1);
for(int i = 1; i <= n; i++){
matriceCosturi[i].push_back(0);
for(int j = 1; j <= n; i++){
fin>>cost;
matriceCosturi[i].push_back(cost);
}
}
Graf graf = Graf(n, true, matriceCosturi);
vector<vector<int>> res = graf.royFloyd();
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; i++){
fout<<res[i][j];
}
}
}
int main() {
ctcInfoArena();
return 0;
}