Pagini recente » Cod sursa (job #756995) | Cod sursa (job #895632) | Cod sursa (job #181554) | Cod sursa (job #1190816) | Cod sursa (job #1737782)
#include <fstream>
#include <cstring>
#include <stack>
#include <vector>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
unsigned int n,m,x,y,node,indx,nrComp=0;
int idx[100005];
int lowLink[100005];
int inStack[100005];
vector<int> graph[100005];
vector<int> ctc[10000];
stack<int> st;
unsigned int min(unsigned int a,unsigned int b) {
if (a>=b)
return b;
return a;
}
void tarjan(unsigned int v) {
idx[v]=indx;
lowLink[v]=indx;
indx++;
st.push(v);
inStack[v]=1;
for (unsigned int u=0;u<graph[v].size();u++) {
if (idx[graph[v][u]]==-1) {
tarjan(graph[v][u]);
lowLink[v]=min(lowLink[v],lowLink[graph[v][u]]);
}
else if (inStack[graph[v][u]])
lowLink[v]=min(lowLink[v],idx[graph[v][u]]);
}
if (idx[v]==lowLink[v]) {
nrComp++;
do {
node=st.top();
st.pop();
inStack[node]=0;
ctc[nrComp].push_back(node);
}while (node!=v);
}
}
void ctcTarjan() {
indx=0;
for (unsigned int i=1;i<=n;i++)
if (idx[i]==-1)
tarjan(i);
}
int main() {
memset(idx,-1,sizeof(idx));
memset(lowLink,0,sizeof(lowLink));
memset(inStack,0,sizeof(inStack));
in>>n>>m;
for (unsigned int i=0;i<m;i++) {
in>>x>>y;
graph[x].push_back(y);
}
ctcTarjan();
out<<nrComp<<"\n";
for (unsigned int i=1;i<=nrComp;i++) {
for (unsigned int j=0;j<ctc[i].size();j++) {
out<<ctc[i][j]<<" ";
}
out<<"\n";
}
return 0;
}