Pagini recente » Cod sursa (job #629701) | Cod sursa (job #414735) | Cod sursa (job #972277) | Cod sursa (job #720304) | Cod sursa (job #641515)
Cod sursa(job #641515)
#include <fstream>
#include <vector>
#include <bitset>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n,i,m,a,b,t=0,tfinal[100001],s[200001],nctc;
vector <int> A[100001];
vector <int> B[100001];
bitset <100001> fr;
bitset <100001> fr2;
bitset <100001> fr3;
void dfs(int nod) {
vector <int>::iterator it;
fr[nod]=1;
tfinal[nod]=++t;
for (it=A[nod].begin();it!=A[nod].end();it++)
if (fr[*it]==0) dfs(*it);
tfinal[nod]=++t;
s[t]=nod;
return;
}
void dfs2(int nod) {
vector <int>::iterator it;
fr2[nod]=1;
for (it=B[nod].begin();it!=B[nod].end();it++)
if (fr2[*it]==0) dfs2(*it);
return ;
}
void dfs3(int nod) {
vector <int>::iterator it;
fr3[nod]=1;
g << nod << ' ';
for (it=B[nod].begin();it!=B[nod].end();it++)
if (fr3[*it]==0) dfs3(*it);
return ;
}
int main () {
f >> n >> m;
for (i=1;i<=m;i++) {
f >> a >> b;
A[a].push_back(b);
B[b].push_back(a);
}
for (i=1;i<=n;i++)
if (fr[i]==0) dfs(i);
for (i=t;i>=1;i--)
if (fr2[s[i]]==0 && s[i]>0) {dfs2(s[i]);nctc++;}
g << nctc << '\n';
for (i=t;i>=1;i--)
if (fr3[s[i]]==0 && s[i]>0) {dfs3(s[i]);g << '\n';}
f.close();g.close();
return 0;
}