Pagini recente » Cod sursa (job #2104299) | Cod sursa (job #508445) | Cod sursa (job #1650340) | Cod sursa (job #1001318) | Cod sursa (job #2055543)
#include<fstream>
#include<list>
#include<stack>
#include<bitset>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int NMAX=100005;
list<int>g[NMAX],scc[NMAX];
stack<int>s;
int scctime[NMAX],low_time[NMAX],n,m,k,node_time=1;
bitset<NMAX>in_stack;
void read_data(){
int from,to;
fin>>n>>m;
while(m--){
fin>>from>>to;
g[from].push_back(to);
}
}
void tarjan(int node){
scctime[node]=low_time[node]=node_time++;
s.push(node);
in_stack[node]=true;
list<int>::iterator it;
for(it=g[node].begin();it!=g[node].end();++it)
if(scctime[*it]==0){
tarjan(*it);
low_time[node]=min(low_time[node],low_time[*it]);
}
else if(in_stack[node])
low_time[node]=min(low_time[node],low_time[*it]);
if(scctime[node]==low_time[node]){
++k;
int sccnode;
do{
sccnode=s.top();
scc[k].push_back(sccnode);
s.pop();
in_stack[sccnode]=false;
}while(node!=sccnode);
}
}
void go_through_vertices(){
int i;
for(i=1;i<=n;++i)
if(!scctime[i])
tarjan(i);
}
void print(){
fout<<k<<'\n';
int i;
list<int>::iterator it;
for(i=1;i<=k;++i){
for(it=scc[i].begin();it!=scc[i].end();++it)
fout<<*it<<' ';
fout<<'\n';
}
}
int main(){
read_data();
go_through_vertices();
print();
}