Pagini recente » Cod sursa (job #2644978) | Cod sursa (job #1116761) | Cod sursa (job #2591073) | Cod sursa (job #1122202) | Cod sursa (job #255480)
Cod sursa(job #255480)
#include<fstream>
#include<vector>
using namespace std;
#define maxn 100009
vector<int> G[maxn], GT[maxn];
vector< vector<int> > Comp;
vector<int> linie;
int viz[maxn], st[maxn];
int n, m, t,nrctc;
int df1(int nod){
viz[nod]=1;
vector<int>::iterator it;
for(it=G[nod].begin();it!=G[nod].end();++it)
if(!viz[*it])
df1(*it);
t++;
st[t]=nod;
}
void topo(){
int i;
for(i=1;i<=n;i++)
if(!viz[i])
df1(i);
}
void df2(int nod){
int i;
vector<int>::iterator it;
viz[nod]=1;
for(it=GT[nod].begin();it!=GT[nod].end();++it)
if(!viz[*it]){
linie.push_back(*it);
df2(*it);
}
}
int main(){
int i, x, y;
ifstream f("ctc.in");
f>>n>>m;
for(i=0;i<m;i++){
f>>x>>y;
G[x].push_back(y);
GT[y].push_back(x);
}
f.close();
topo();
for(i=1;i<=n;i++)
viz[i]=0;
for(i=t;i>0;i--)
if(!viz[st[i]]){
linie.push_back(st[i]);
df2(st[i]);
Comp.push_back(linie);
linie.resize(0);
++nrctc;
}
vector<int>::iterator it;
ofstream g("ctc.out");
g<<nrctc<<'\n';
for(i=0;i<nrctc;i++){
for(it=Comp[i].begin();it!=Comp[i].end();++it)
g<<*it<<' ';
g<<'\n';
}
g.close();
return 0;
}