Pagini recente » Cod sursa (job #3199719) | Cod sursa (job #2496885) | Cod sursa (job #1385897) | Cod sursa (job #1227629) | Cod sursa (job #2798725)
#include <bits/stdc++.h>
using namespace std;
ifstream fin( "ctc.in" );
ofstream fout( "ctc.out" );
class Graf {
private:
int N;
vector< vector<int> > adc, adc2;
vector<int> viz, sortate;
void DfsSortare(int nod);
void DfsTareConexe(int node, vector<int> &a);
public:
Graf( int n );
void AdaugaMuchie( int x, int y);
vector<int>Sortare();
void CompTareConexe();
};
void Graf :: DfsSortare(int nod) {
int i, w;
viz[nod] = 1;
for(i = 0; i < adc[nod].size(); i++) {
w = adc[nod][i];
if(viz[w] == 0)
DfsSortare(w);
}
sortate.push_back(nod);
}
void Graf :: DfsTareConexe(int nod, vector<int> &a) {
viz[nod] = 1;
for(int i = 0; i < adc2[nod].size(); i++) {
int w = adc2[nod][i];
if( viz[w] == 0 )
DfsTareConexe(w, a);
}
a.push_back(nod);
}
Graf :: Graf(int n) {
N = n;
adc.resize(n + 1);
adc2.resize(n + 1);
viz.resize(n + 1);
}
void Graf :: AdaugaMuchie(int x, int y) {
adc[x].push_back(y);
adc2[y].push_back(x);
}
vector<int> Graf :: Sortare() {
for( int i = 1; i <= N; i++ )
viz[i] = 0;
for( int i = 1; i <= N; i++ )
if( viz[i] == 0 )
DfsSortare(i);
return sortate;
}
void Graf :: CompTareConexe() {
vector<vector<int> > a;
vector<int> v_sortat = Sortare();
int curr, i, j;
for(i = 0; i <= N; i++)
viz[i] = 0;
for(i = v_sortat.size() - 1; i >= 0; i--) {
vector<int> ctc;
curr = v_sortat[i];
if(viz[curr]) continue;
DfsTareConexe(curr, ctc);
a.push_back(ctc);
}
fout<<a.size()<<"\n";
for(i = 0 ; i < a.size(); i++){
for(j = 0; j < a[i].size(); j++)
fout<<a[i][j]<<" ";
fout<<"\n";
}
}
int main()
{
int i, n, m, x, y;
fin >> n >> m;
Graf G(n);
for(i = 1; i <= m; i++) {
fin>>x>>y;
G.AdaugaMuchie(x, y);
}
G.CompTareConexe();
return 0;
}