Pagini recente » Cod sursa (job #2532462) | Cod sursa (job #1571977) | Cod sursa (job #659221) | Cod sursa (job #1022998) | Cod sursa (job #2798586)
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
using namespace std;
void dfs( int k, vector < vector < int > > &vecini, vector < int > &culoare, vector < int > &s ){
culoare[k] = 1;
for( int i = 0; i < vecini[k].size(); i++ ){
if( culoare[ vecini[k][i] ] == 0 ){
dfs( vecini[k][i], vecini, culoare, s );
}
}
s.push_back(k);
}
void dfsT( int k, vector < vector < int > > &vecini, vector < int > &culoare, vector < int > & graf){
culoare[k] = 1;
graf.push_back(k);
for( int i = 0; i < vecini[k].size(); i++ ){
if( culoare[ vecini[k][i] ] == 0 ){
dfsT( vecini[k][i], vecini, culoare, graf );
}
}
}
int main(){
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector < vector < int > > vecini;
vector < vector < int > > transpus;
vector < int > culoare;
vector < int > s;
int nr_noduri, nr_muchii;
fin >> nr_noduri >> nr_muchii;
for(int i = 0; i <= nr_noduri; i++){
vector < int > v;
vecini.push_back(v);
transpus.push_back(v);
}
for( int i = 0; i < nr_muchii; i++ ){
int intrare, iesire;
fin >> intrare >> iesire;
vecini[intrare].push_back(iesire);
transpus[iesire].push_back(intrare);
}
for( int i = 0; i <= nr_noduri; i++ ){
culoare.push_back(0);
}
for( int i = 1; i <= nr_noduri; i++ ){
if( culoare[i] == 0 ){
dfs(i, vecini, culoare, s);
}
}
int contor = 0;
vector < vector < int > > grafuri;
for( int i = s.size() - 1; i >= 0; i-- ){
if( culoare[ s[i] ] == 0 ){
contor++;
vector < int > graf;
dfsT( s[i] , transpus, culoare, graf);
grafuri.push_back(graf);
}
}
fout << contor << endl;
for( int i = 0; i < grafuri.size(); i++ ){
for( int j = 0; j < grafuri[i].size(); j++ ){
fout << grafuri[i][j] << " ";
}
fout << '\n';
}
}