Pagini recente » Cod sursa (job #2569878) | Cod sursa (job #2938026) | Cod sursa (job #3125101) | Cod sursa (job #1816763) | Cod sursa (job #2797096)
#include<bits/stdc++.h>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector<int> adjList[100001],adjListTrans[100001],ctc[100001];
vector<int> visited;
stack<int> st;
vector<int> nodes;
void DFS(int x){
int i;
for(i=0;i<adjList[x].size();++i){
if(visited[adjList[x][i]-1]==0){
visited[adjList[x][i]-1]++;
st.push(adjList[x][i]);
//cout<<adjList[x][i]<<' ';
DFS(adjList[x][i]);
}
}
}
void Kosaraju(int x,int node){
int i;
for(i=0;i<adjListTrans[x].size();++i){
if(visited[adjListTrans[x][i]-1]==1){
visited[adjListTrans[x][i]-1]++;
ctc[node].push_back(adjListTrans[x][i]);
Kosaraju(adjListTrans[x][i],node);
}
}
}
int main(){
int n,m,i,a,b;
f>>n>>m;
for(i=0;i<n;++i)
visited.push_back(0);
for(i=0;i<m;++i){
f>>a>>b;
adjList[a].push_back(b);
adjListTrans[b].push_back(a);
}
for(i=0;i<visited.size();++i){
if(visited[i]==0){
visited[i]++;
// cout<<i+1<<' ';
st.push(i+1);
DFS(i+1);
}
}
int count=0;
while(!st.empty()){
int node=st.top();
if(visited[node-1]==1){
visited[node-1]++;
nodes.push_back(node);
ctc[node].push_back(node);
count++;
Kosaraju(node,node);
}
st.pop();
}
g<<count<<'\n';
int j;
for(i=0;i<nodes.size();++i){
for(j=0;j<ctc[nodes[i]].size();++j){
g<<ctc[nodes[i]][j]<<' ';
}
g<<'\n';
}
return 0;
}