Pagini recente » Cod sursa (job #767200) | Cod sursa (job #282697) | Statistici GEORGE34567 (George3456likes_piezisa) | Cod sursa (job #373141) | Cod sursa (job #3148906)
//We want to split a group of n people (labeled from 1 to n) into two groups of any size. Each person may dislike some other people,
//and they should not go into the same group.
//Given the integer n and the array dislikes where dislikes[i] = [ai, bi] indicates that the person labeled ai does not like the person labeled bi,
//return true if it is possible to split everyone into two groups in this way.
// Mai pe scurt acesta este un BFS putin diferit
//#include <bits/stdc++.h>
//
//using namespace std;
//
//ifstream fin("graf.in");
//ofstream fout("graf.out");
//
//const int MAX = 2001;
//int n, m;
//bool isBipartite;
//int adj[MAX][MAX], viz[MAX];
//queue<int> q;
//
//void BFS(){
// q.push(1);
// viz[1] = 1;
// while(!q.empty()){
// int aux = q.front();
// q.pop();
// for(int i = 1; i <= n; i++){
// if(viz[aux] == viz[i] && adj[aux][i] == 1){
// isBipartite = false;
// return;
// }
// else if(adj[aux][i] == 1 && viz[i] == 0){
// q.push(i);
// if(viz[aux] == 1){
// viz[i] = 2;
// }
// else{
// viz[i] = 1;
// }
// }
// }
// }
//}
//
//int main() {
//
// fin >> n >> m;
// for(int i = 1; i <= m; i++){
// int x, y;
// fin >> x >> y;
// adj[x][y] = adj[y][x] = 1;
// }
// isBipartite = true;
// BFS();
// if(!isBipartite){
// fout << "False" << endl;
// }
// else{
// fout << "True" << endl;
// for(int i = 1; i <= n; i++){
// if(viz[i] == 1){
// fout << i << ' ';
// }
// }
// fout<<endl;
// for(int i = 1; i <= n; i++){
// if(viz[i] == 2){
// fout << i << ' ';
// }
// }
// fout<<endl;
// }
//
// return 0;
//}
//
//One of the most popular algorithms for traversing a graph is the Depth First Search (DFS).
//The DFS is usually implemented as a recursive function. First we call the function for the starting node.
//For each call, we go through the adjacency list of the current node, and recursively call the function for the unvisited neighbours.
//Notice that if we permute the adjacency lists of the nodes, the order in which we visit them might differ.
//In this problem you are given a graph with N nodes and M edges and a permutation P of size N.
//If you are allowed to shuffle the adjacency lists, is it possible to visit the nodes during a DFS starting in node
//1 in the order given by P?
//Mai pe scurt acesta este un DFS care are o sortare in fiecare lista de adiacenta!
//#include <bits/stdc++.h>
//
//using namespace std;
//
//ifstream fin("graf.in");
//ofstream fout("graf.out");
//
//const int MAX = 1e5 + 3;
//int n, m;
//vector<int> adj[MAX], dfs_order;
//int ord[MAX], viz[MAX];
//
//
//int compara(int a, int b){
// return ord[a] < ord[b];
//}
//
//void DFS(int node){
// viz[node] = 1;
// dfs_order.push_back(node);
// for(auto vecin : adj[node]){
// if(viz[vecin] == 0){
// DFS(vecin);
// }
// }
//}
//
//int main() {
//
// fin >> n >> m;
// vector<int> permutare(n);
// for(int i = 1; i <= n; i++){
// int aux;
// fin >> aux;
// ord[aux] = i;
// permutare[i - 1] = aux;
// }
//
//
// for(int i = 1; i <= m; i++){
// int x, y;
// fin >> x >> y;
// adj[x].push_back(y);
// adj[y].push_back(x);
// }
// for(int i = 1; i <= n; i++){
// sort(adj[i].begin(), adj[i].end(), compara);
// }
//
// DFS(1);
// // fout << "dfs_order : " << endl;
// // for(int i = 0; i < n ; i++){
// // fout << dfs_order[i] << ' ';
// // }
// // fout << endl << "permutare : \n";
// // for(int i = 0; i < n; i++){
// // fout << permutare[i] << ' ';
// // }
// fout << (permutare == dfs_order) << endl;
//
// return 0;
//}
//There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where
//prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.
//For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.
//Return the ordering of courses you should take to finish all courses. If there are many valid answers,
//return any of them. If it is impossible to finish all courses, return an empty array.
//
//Problema cu cursurile adica un graf orientat in care trebuie sa aflam daca avem ciclu sau nu. Nu e terminata aici.
//#include <bits/stdc++.h>
//
//using namespace std;
//
//ifstream fin("graf.in");
//ofstream fout("graf.out");
//const int MAX = 1e4 + 1;
//int n, m;
//vector<int> adj[MAX], viz, cur_path, rezultat;
//vector<int> DFS(int node){
//
// if(viz[node]){
// return {};
// }
// if(cur_path[node]){
// return {node};
// }
//
// viz[node] = 1;
// cur_path[node] = 1;
// for(auto vecin : adj[node]){
// vector<int> ciclu = DFS(vecin);
// if(!ciclu.empty()){
// return ciclu;
// }
// }
// cur_path[node] = 0;
// rezultat.push_back(node);
// return {};
//}
//
//int main() {
// fin >> n >> m;
// for(int i = 1; i <= m; i++){
// int x, y;
// fin >> x >> y;
// adj[y].push_back(x);
// }
// int ans = 1;
// for(int i = 1; i <= n; i++){
// if(!viz[i]){
// vector<int> ciclu = DFS(i);
// if(!ciclu.empty()){
// ans = 0;
// }
// }
// }
//
//
// return 0;
//}
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int MAX = 1e5 + 1, NEVIZITAT = -1;
int n, m, id, sccCount, ids[MAX], low[MAX];
vector<int> adj[MAX], cur_path[MAX];
stack<int> stiva;
vector<bool> onStack(MAX, false);
void DFS(int node){
onStack[node] = true;
stiva.push(node);
ids[node] = low[node] = id++;
for(auto vecin : adj[node]){
if(ids[vecin] == NEVIZITAT){
DFS(vecin);
}
if(onStack[vecin]){
low[node] = min(low[node], low[vecin]);
}
}
if(low[node] == ids[node]){
while(!stiva.empty()){
int aux = stiva.top();
stiva.pop();
cur_path[sccCount].push_back(aux);
onStack[aux] = false;
low[aux] = ids[node];
if(aux == node){
break;
}
}
sccCount++;
}
}
int main() {
fin >> n >> m;
for(int i = 1; i <= m; i++){
int x, y;
fin >> x >> y;
adj[x].push_back(y);
}
for(int i = 1; i <= n; i++){
ids[i] = NEVIZITAT;
}
for(int i = 1; i <= n; i++){
if(ids[i] == NEVIZITAT){
DFS(i);
}
}
fout << sccCount << endl;
for(int i = 0 ; i < sccCount; i++){
for(auto cmp : cur_path[i]){
fout << cmp << ' ';
}
fout << endl;
}
return 0;
}