Pagini recente » Cod sursa (job #206389) | Cod sursa (job #688410) | Cod sursa (job #433884) | tema | Cod sursa (job #2502793)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
int n, m;
bool viz[100001], showTime;
vector<int> G[100001];
vector<int> GT[100001];
int nr;
vector<int> SCC[100001];
stack<int> s;
void DFSTareConex(int i);
void GetT();
void ShowSCC();
void DFS(int i);
void printG();
int main(){
in>>n>>m;
for(int l = 0; l < m; l++){
int i, j;
in>>i>>j;
G[i].push_back(j);
}
for(int i = 1; i <= n; i++){
viz[i] = false;
}
for(int i = 1; i <= n; i++){
if(viz[i] == false)
DFSTareConex(i);
}
GetT();
ShowSCC();
//printG();
return 0;
}
void printG(){
for(int i = 1; i <= n; i++){
out<<i<<" ";
for(int j = 0; j < GT[i].size(); j++){
out<<G[i].at(j)<<" ";
}
out<<"\n";
}
}
void DFSTareConex(int i){
viz[i] = true;
for(int l = 0; l < G[i].size(); l++){
int n = G[i].at(l);
if(viz[n] == false){
DFSTareConex(n);
}
}
s.push(i);
}
void GetT(){
for(int i = 1; i <= n; i++){
for(int j = 0; j < G[i].size(); j++){
int n = G[i].at(j);
GT[n].push_back(i);
}
}
}
void ShowSCC(){
for(int i = 1; i <= n; i++){
viz[i] = false;
}
while(!s.empty()){
int i = s.top();
s.pop();
if(viz[i] == false){
nr++;
DFS(i);
}
}
out<<nr<<"\n";
for(int i = 1; i <= nr; i++){
for(int j = 0; j < SCC[i].size(); j++){
out<<SCC[i].at(j)<<" ";
}
out<<"\n";
}
}
void DFS(int i){
viz[i] = true;
SCC[nr].push_back(i);
for(int j = 0; j < GT[i].size(); j++){
int n = GT[i].at(j);
if(viz[n] == false){
DFS(n);
}
}
}