Pagini recente » Cod sursa (job #717130) | Cod sursa (job #1519862) | Cod sursa (job #644401) | Cod sursa (job #528729) | Cod sursa (job #526946)
Cod sursa(job #526946)
#include <fstream>
#include <stack>
using namespace std;
#define NMAX 100000
struct list {
int id;
list* next;
};
int N, M;
bool visited[NMAX+1];
list* adj_list[NMAX+1];
list* adj_list_inverted[NMAX+1];
list* ctc_list[NMAX+1];
stack<int> stiva;
int ctc_count = 0;
void readInput();
void dfs(int s);
void dfsT(int s);
int main(void)
{
readInput();
for (int i=1;i<=N;i++)
{
if (!visited[i])
dfs(i);
}
for (int i=1;i<=N;i++)
visited[i] = false;
while (!stiva.empty())
{
int v = stiva.top();
stiva.pop();
if (!visited[v])
{
ctc_count++;
dfsT(v);
}
}
ofstream g("ctc.out");
g << ctc_count << "\n";
for (int i=1;i<=ctc_count;i++)
{
list* it = ctc_list[i];
while (it != NULL)
{
g << it->id << " ";
it = it->next;
}
g << "\n";
}
g.close();
return 0;
}
void readInput()
{
int from, to;
ifstream f("ctc.in");
f >> N >> M;
for (int i=1;i<=M;i++)
{
f >> from >> to;
list* x = new list;
x->id = to;
x->next = adj_list[from];
adj_list[from] = x;
x = new list;
x->id = from;
x->next = adj_list_inverted[to];
adj_list_inverted[to] = x;
}
f.close();
}
void dfs(int s)
{
visited[s] = true;
list* it = adj_list[s];
while (it != NULL)
{
if (!visited[it->id])
{
dfs(it->id);
}
it = it->next;
}
stiva.push(s);
}
void dfsT(int s)
{
visited[s] = true;
list* it = adj_list_inverted[s];
while (it != NULL)
{
if (!visited[it->id])
{
dfsT(it->id);
}
it = it->next;
}
list* x = new list;
x->id = s;
x->next = ctc_list[ctc_count];
ctc_list[ctc_count] = x;
}