Pagini recente » Cod sursa (job #1074991) | Cod sursa (job #3186236) | Cod sursa (job #2121887) | Cod sursa (job #1875790) | Cod sursa (job #630280)
Cod sursa(job #630280)
#include<cstdio>
#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), 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;
printf("%d ", adiacent);
}
while (nod != adiacent);
printf("\n");
}
}
int main(){
freopen("ctc.in", "r", stdin), freopen("componente.txt", "w", stdout);
scanf("%d %d", &n, &m);
int i, x, y;
for (i = 0; i < m; i++) {
scanf("%d %d", &x, &y);
graf[x].push_back(y);
}
for (i = 1; i <= n ; i++){
if (!viz[i]) SCC(i);
}
fclose(stdin), fclose(stdout);
freopen("componente.txt", "r", stdin), freopen("ctc.out", "w", stdout);
printf ("%d\n", nrComp);
char line[1000001];
scanf("%1000000[0-9 \n]s", line);
printf("%s\n", line);
fclose(stdin), fclose(stdout);
return 0;
}