Pagini recente » Cod sursa (job #860719) | Cod sursa (job #1648512) | Cod sursa (job #2440332) | Cod sursa (job #2939038) | Cod sursa (job #656580)
Cod sursa(job #656580)
// componente tare conexe
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#include <iterator>
#define NMAX 100011
using namespace std;
vector <int> G[NMAX],con;
stack <int> S;
vector <vector<int> > C;
int n,m,niv;
int idx[NMAX],lowlink[NMAX];
bool in_s[NMAX];
inline int minim(int a, int b){
if(a<=b) return a;
return b;
}
void read(){
int i,x,y;
ifstream f("ctc.in");
f>>n>>m;
for(i=1;i<=m;++i){
f>>x>>y;
G[x].push_back(y);
idx[i]=-1;
}
}
void dfs(int nod){
idx[nod]=lowlink[nod]=niv;
niv++;
S.push(nod); in_s[nod]=true;
for(vector <int>::iterator it=G[nod].begin(); it!=G[nod].end(); ++it) {
if(idx[*it]==-1) dfs(*it), lowlink[nod]=minim(lowlink[nod],lowlink[*it]);
else if(in_s[*it]==true)
lowlink[nod]=minim(lowlink[nod],lowlink[*it]);
}
if(idx[nod]==lowlink[nod]){
con.clear();
int node;
do{
con.push_back(node=S.top());
S.pop(), in_s[node]=false;
}
while(node!=nod);
C.push_back(con);
}
}
void write(){
ofstream g("ctc.out");
g<<C.size()<<"\n";
for(size_t i=0;i<C.size();++i){
for(size_t j=0;j<C[i].size();++j)
g<<C[i][j]<<" ";
g<<"\n";
}
}
int main(){
read();
for(int i=1;i<=n;++i)
if(idx[i]==-1) dfs(i);
write();
return 0;
}