Pagini recente » Cod sursa (job #2221976) | Cod sursa (job #1050061) | Cod sursa (job #1769611) | Cod sursa (job #262062) | Cod sursa (job #632681)
Cod sursa(job #632681)
#include<fstream>
#include<vector>
#define min(a,b) a<b ? a : b
using namespace std;
int n, m, index = 1, nrComp = 0;
vector <int> graf[100001], S, vindex(100001, 0), lowlink(100001, 200001);
vector <int> compCurenta(100001, 0), sol[100001], viz(100001, 0);
void SCC(int nod){
S.push_back(nod);
vindex[nod] = index;
lowlink[nod] = index++;
compCurenta[nod] = 1;
viz[nod] = 1;
int i, adiacent;
for (i = 0; i < (int) graf[nod].size(); i++){
adiacent = graf[nod][i];
if (vindex[adiacent] == 0) {
SCC( adiacent );
lowlink[nod] = min (lowlink[adiacent], lowlink[nod]);
}
else if (compCurenta[adiacent] == 1)
lowlink[nod] = min (vindex[adiacent], lowlink[nod]);
}
if (lowlink[nod] == vindex[nod]){
nrComp++;
do {
adiacent = S[S.size() - 1];
S.pop_back();
compCurenta[adiacent] = 0;
sol[nrComp].push_back(adiacent);
}
while (nod != adiacent);
}
}
int main(){
ifstream fin ("ctc.in");
fin >> n >> m;
int i, x, y;
for (i = 0; i < m; i++) {
fin >> x >> y;
graf[x].push_back(y);
}
for (i = 1; i <= n ; i++){
if (!viz[i]) SCC(i);
}
ofstream fout("ctc.out");
fout << nrComp <<"\n";
for (int i = 1; i <= nrComp; i++){
for (int j = 0; j < (int) sol[i].size(); j++) fout << sol[i][j] << " ";
fout << "\n";
}
return 0;
}